<p>Given two strings <code>str1</code> and <code>str2</code>, return <em>the shortest string that has both </em><code>str1</code><em> and </em><code>str2</code><em> as <strong>subsequences</strong></em>. If there are multiple valid strings, return <strong>any</strong> of them.</p>

<p>A string <code>s</code> is a <strong>subsequence</strong> of string <code>t</code> if deleting some number of characters from <code>t</code> (possibly <code>0</code>) results in the string <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> str1 = &quot;abac&quot;, str2 = &quot;cab&quot;
<strong>Output:</strong> &quot;cabac&quot;
<strong>Explanation:</strong> 
str1 = &quot;abac&quot; is a subsequence of &quot;cabac&quot; because we can delete the first &quot;c&quot;.
str2 = &quot;cab&quot; is a subsequence of &quot;cabac&quot; because we can delete the last &quot;ac&quot;.
The answer provided is the shortest such string that satisfies these properties.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> str1 = &quot;aaaaaaaa&quot;, str2 = &quot;aaaaaaaa&quot;
<strong>Output:</strong> &quot;aaaaaaaa&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= str1.length, str2.length &lt;= 1000</code></li>
	<li><code>str1</code> and <code>str2</code> consist of lowercase English letters.</li>
</ul>

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        ## Finding Longest common subsequence
        if len(str1) < len(str2):
            str1, str2 = str2, str1

        n1 = len(str1)
        n2 = len(str2)

        prev_dp_list = [[] for _ in range(n2)]

        if str1[0] == str2[0]:
            prev_dp_list[0] = [str1[0]]
        else:
            prev_dp_list[0] = []

        for j in range(1,n2):
            prev_dp_list[j] = prev_dp_list[j-1][:]
            if str2[j] == str1[0] and len(prev_dp_list[j-1]) == 0:
                prev_dp_list[j] = [str2[j]]
            
        # print(prev_dp_list)

        for i in range(1,n1):
            curr_dp_list = [[] for _ in range(n2)]
            curr_dp_list[0] = prev_dp_list[0][:]
            if str1[i] == str2[0] and len(prev_dp_list[0]) == 0:
                curr_dp_list[0].append(str1[i])

            for j in range(1,n2):
                if str1[i] == str2[j]:
                    curr_dp_list[j] = prev_dp_list[j-1]
                    curr_dp_list[j].append(str1[i])
                else:
                    if len(curr_dp_list[j-1]) < len(prev_dp_list[j]):
                        curr_dp_list[j] = prev_dp_list[j][:]
                    else:
                        curr_dp_list[j] = curr_dp_list[j-1][:]

            prev_dp_list = curr_dp_list

        output_string_list = []
        p1, p2, p3 = 0, 0, 0
        while p1 <= n1-1 and p2 <= n2-1 and p3 <= len(curr_dp_list[n2-1])-1:
            while p1 <= n1-1 and str1[p1] != curr_dp_list[n2-1][p3]:
                output_string_list.append(str1[p1])
                p1 += 1
            while p2 <= n2-1 and str2[p2] != curr_dp_list[n2-1][p3]:
                output_string_list.append(str2[p2])
                p2 += 1
            output_string_list.append(curr_dp_list[n2-1][p3])
            p1 += 1
            p2 += 1
            p3 += 1

        while p1 <= n1-1:
            output_string_list.append(str1[p1])
            p1 += 1

        while p2 <= n2-1:
            output_string_list.append(str2[p2])
            p2 += 1

        return ''.join(output_string_list)

        # @cache
        # def dp(p1,p2):
        #     if p1 < 0 and p2 < 0:
        #         return []
        #     if p1 < 0:
        #         return [str2[i] for i in range(p2+1)]
        #     if p2 < 0:
        #         return [str1[i] for i in range(p1+1)]

        #     if str1[p1] == str2[p2]:
        #         return dp(p1-1,p2-1) + [str1[p1]]

        #     if len(dp(p1-1,p2)) < len(dp(p1,p2-1)):
        #         return dp(p1-1,p2) + [str1[p1]]

        #     return dp(p1,p2-1) + [str2[p2]]

        # return ''.join(dp(n1-1, n2-1))

        # def lps_builder(pattern):
        #     m = len(pattern)
        #     prev, i = 0, 1

        #     lps = [0 for _ in range(m)]
        #     while i <= m-1:
        #         if pattern[i] == pattern[prev]:
        #             lps[i] = prev + 1
        #             i += 1
        #             prev += 1
        #         else:
        #             if prev == 0:
        #                 i += 1
        #             else:
        #                 prev = lps[prev-1]

        #     return lps

        # def KMP_match(text, pattern, lps): ## gives longest suffix in text that matches with prefix in pattern
        #     n = len(text)
        #     i = max(0, n-len(pattern))
        #     j = 0

        #     while i <= n-1:
        #         if text[i] == pattern[j]:
        #             i += 1
        #             j += 1
        #         else:
        #             if j == 0:
        #                 i += 1
        #             else:
        #                 j = lps[j-1]

        #     return j


        # lps_pattern1 = lps_builder(str1)
        # lps_pattern2 = lps_builder(str2)
        # n1 = len(str1)
        # n2 = len(str2)

        # max_match_str1_before_str2 = KMP_match(str1, str2, lps_pattern2)
        # max_match_str2_before_str1 = KMP_match(str2, str1, lps_pattern1)

        # print(max_match_str1_before_str2, max_match_str2_before_str1)

        # if max_match_str1_before_str2 > max_match_str2_before_str1:
        #     if max_match_str1_before_str2 <= n2-1:
        #         return str1+str2[max_match_str1_before_str2:]
        #     return str1
        
        # if max_match_str2_before_str1 <= n1-1:
        #     return str2+str1[max_match_str2_before_str1:]

        # return str2
        
24466