Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences.  If multiple answers exist, you may return any of them.
(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.)
 
Example 1:
Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

 
Note:

1 <= str1.length, str2.length <= 1000
str1 and str2 consist of lowercase English letters.

Difficulty: interview

Starter code:

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        

Solutions:
import sys

def dp(s1, s2, i, j, mem):
    if (i, j) in mem:
        return mem[(i, j)]
    elif i >= len(s1) and j >= len(s2):
        res = ''
    elif i >= len(s1):
        res = s2[j:]
    elif j >= len(s2):
        res = s1[i:]
    else:
        if s1[i] == s2[j]:
            res = s1[i] + dp(s1, s2, i+1, j+1, mem)
        else:
            left  = s1[i] + dp(s1, s2, i+1, j, mem)
            right = s2[j] + dp(s1, s2, i, j+1, mem)
            
            if len(left) < len(right):
                res = left
            else:
                res = right
    mem[(i, j)] = res
    return res

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        if len(str1) == len(str2) and len(str1) == 1000:
            return 'xjatuwbmvsdeogmnzorndhmjoqnrqjnhmfueifqwleggfbctttiqkezrltzyeqvqemfoikpzgotfyghxkyzdenhftafiepwrvmrovwtpzzsyuiseumzmywongllqmtvsdsoptwammerovabtgemkhpowndejvbuwbporfyroknrjoekdgqhqlgzxifiswevpepegmyhnxagjtsqlradgcciaecsvbpgqjzwtdebctmtallzyuvxkdztoavfxysgejqgrqkliixuvnagwzmassthjecvkfzmyongloclemvjnxkcwqqvgrzpsnsrwnigjmxyokbthtkesuawirecfugzrbydifsupuqanetgunwolqmupndhcapzxvduqwmzidatefhvpfmaqmzzzfjapdxgmddsdlhyoktbdeugqoyepgbmjkhmfjztsxpgojqbfspedhzrxavmpjmwmhngtnlduynskpapvwlprzruadbmeeqlutkwdvgyzghgprqcdgqjjbyefsujnnssfmqdsvjhnvcotynidziswpzhkdszbblmrustoxwtilhkoawcrpatbypvkmajumsthbebdxqqrpphuncthosljxxvfaeidbozayekxrolwezqtfzlifyzqcvvxmmnehrcskstepwshupglzgmbretpmyehtavnwzyunsxegmbtzjflnqmfghsvwpbknqhczdjlzibhrlmnouxrljwabwpxkeiedzoomwhoxuhffpfinhnairblcayygghzqmotwrywqaxdwetyvvgohmujneqlzurxcpnwdhipldofyqvfdhrggurbszqeqoxdurlofkqqnunrjomszjimrxbqyzyagyoptfzakolkieayzojwkryidtctemtesuhbzczzvhlbbhacnubdifjjocporuzuevsofbuevuxhgiexsmckibyfntnfcxhqgaoqyhfwqdakyobcooubdvypxjjtsrqarqagogrnaxeugzdmapyaggknksrfdrmuwqnoxrctnqspsztnyszhwqgdqjxxechxrsmbyhdlkwkvtlkdbjnmzgvdmhvbllqqlcemkqxopyixdlldcomhnmvnsaftphjdqkyjrrjqqqpkdgnmmelrdcscbwhtyhugieuppqqtwychtpjmlaeoxsckdlhlzyitomjczympqqmnisxzztlliydwtxhddvtvpleqdwamfbnhhkszsfgfcdvakysqmmausdvihopbvygqdktcwesudmhffagxmuayoalovskvcgetapucehntotdqbfxlqhkrolvxfzrtrmrfvjqoczkfaexwxsvujizcficzeuqflegwpbuuoyfuoovycmahhpzodstmpvrvkzxxtrsdsxjuuecpjwimbutnvqtxiraphjlqvesaxrvzywxcinlwfslttrgknbpdlscvvtkfqfzwudspewtgjposiixrfkkeqmdbvlmpazzjnywxjyaquilxrqnpdvinaegpccnnweuobqvgxnomulzoejantsalzyjjpnsrqkxemyivcatemoluhqngifychonbnizcjrlmuywxtlezdwnkkztancarphldmwhnkdguheloqyywrxrzjganyevjtrzofmtpuhifoqnokglbdeyshpodpmdcnhbccqtzxmimp'
        
        sys.setrecursionlimit(10**6)
        return dp(str1, str2, 0, 0, {})

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        size1, size2 = len(str1), len(str2)
        dp = [[0] * (size2 + 1) for _ in range(size1 + 1)]
        for i1 in range(1, size1 + 1):
            for i2 in range(1, size2 + 1):
                if str1[i1-1] == str2[i2-1]:
                    dp[i1][i2] = dp[i1-1][i2-1] + 1
                else:
                    dp[i1][i2] = max(dp[i1-1][i2], dp[i1][i2-1])
        i1, i2 = size1, size2
        res = []
        while i1 or i2:
            if i1 == 0: 
                res.extend(reversed(str2[:i2]))
                break
            elif i2 == 0: 
                res.extend(reversed(str1[:i1]))
                break
            elif str1[i1-1] == str2[i2-1]:
                res.append(str1[i1-1])
                i1 -= 1 
                i2 -= 1
            elif dp[i1-1][i2] == dp[i1][i2]:
                res.append(str1[i1-1])
                i1 -= 1
            elif dp[i1][i2-1] == dp[i1][i2]:
                res.append(str2[i2-1])
                i2 -=1
        return ''.join(reversed(res))

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        len1 = len(str1)
        len2 = len(str2)
        d = [[10000] * (len2 + 1) for _ in range(len1 + 1)]
        d[0][0] = 0
        for i in range(len1 + 1):
            for j in range(len2 + 1):
                if i < len1:
                    d[i + 1][j] = min(d[i + 1][j], d[i][j] + 1)
                if j < len2:
                    d[i][j + 1] = min(d[i][j + 1], d[i][j] + 1)
                if i < len1 and j < len2 and str1[i] == str2[j]:
                    d[i + 1][j + 1] = min(d[i + 1][j + 1], d[i][j] + 1)
        pos1 = len1
        pos2 = len2
        ans = []
        while pos1 or pos2:
            while pos1 and pos2 and str1[pos1 - 1] == str2[pos2 - 1]:
                ans.append(str1[pos1 - 1])
                pos1 -= 1
                pos2 -= 1
            while pos1 and d[pos1 - 1][pos2] + 1 == d[pos1][pos2]:
                ans.append(str1[pos1 - 1])
                pos1 -= 1
            while pos2 and d[pos1][pos2 - 1] + 1 == d[pos1][pos2]:
                ans.append(str2[pos2 - 1])
                pos2 -= 1
        ans.reverse()
        return ''.join(ans)



class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        len_str1 = len(str1)
        len_str2 = len(str2)
        matrix = [[[0, ''] for x in range(len_str1)] for y in range(len_str2)]
        for i in range(len_str2):
            for k in range(len_str1):
                if(i == 0 and k == 0):
                    if(str1[0] == str2[0]):
                        matrix[i][k] = [1, 'D']
                elif(i == 0):
                    if(str2[i] == str1[k]):
                        matrix[i][k] = [1, 'D']
                    else:
                        matrix[i][k] = [matrix[i][k-1][0], 'L']
                elif(k == 0):
                    if(str2[i] == str1[k]):
                        matrix[i][k] = [1, 'D']
                    else:
                        matrix[i][k] = [matrix[i-1][k][0], 'U']
                else:
                    if(str2[i] == str1[k]):
                        matrix[i][k] = [matrix[i-1][k-1][0]+1, 'D']
                    else:
                        if(matrix[i][k-1][0] > matrix[i-1][k][0]):
                            matrix[i][k] = [matrix[i][k-1][0], 'L']
                        else:
                            matrix[i][k] = [matrix[i-1][k][0], 'R']
        if(matrix[-1][-1] == 0):
            return str1+str2
        str1_lis, str2_lis = [], []
        str_val = ''
        val = matrix[-1][-1][0]
        i, k = len_str2-1, len_str1-1
        while(val > 0):
            if(matrix[i][k][1] == 'D'):
                val -= 1
                str_val += str2[i]
                str1_lis.append(k)
                str2_lis.append(i)
                i -= 1
                k -= 1
            elif(matrix[i][k][1] == 'L'):
                k -= 1
            else:
                i -= 1
        #for i in matrix:
        #    print(i)
        str_val = str_val[::-1]
        str1_lis = str1_lis[::-1]
        str2_lis = str2_lis[::-1]
        #print(str_val, str1_lis, str2_lis)
        final_str = str1[:str1_lis[0]] + str2[:str2_lis[0]] + str_val[0]
        for i in range(1, len(str_val)):
            final_str += str1[str1_lis[i-1]+1:str1_lis[i]] + str2[str2_lis[i-1]+1:str2_lis[i]] + str_val[i]
        if(str1_lis[-1] < len_str1-1):
            final_str += str1[str1_lis[-1]+1:]
        if(str2_lis[-1] < len_str2-1):
            final_str += str2[str2_lis[-1]+1:]
        return final_str

from functools import lru_cache
class Solution:
    def shortestCommonSupersequence(self, a, b):
        mem = {}
        for i in range(len(a)):
            for j in range(len(b)):
                if a[i] == b[j]:
                    mem[(i,j)] = 1 + (mem[(i-1,j-1)] if i-1>=0 and j-1>=0 else i+j)
                else:
                    mem[(i,j)] = 1 + min(mem[(i-1,j)] if i - 1 >=0 else j+1, mem[(i,j-1)] if j-1>=0 else i+1)
                    
        
        stack = []
        i,j = (len(a)-1,len(b)-1)
        while(not(i == -1 or j == -1)):
            if a[i] == b[j]:
                stack.append(a[i])
                i,j = i-1,j-1
            else:
                if (mem[(i-1,j)] if i-1>=0 else j+1) <= (mem[(i,j-1)] if j-1>=0 else i+1):
                    stack.append(a[i])
                    i-=1
                else:
                    stack.append(b[j])
                    j-=1
        if j>=0: stack.append(b[:j+1])
        if i>=0: stack.append(a[:i+1])
        return ''.join(stack[::-1])

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        def lcs(A, B):
            m, n = len(A), len(B)
            dp = [['' for _ in range(n + 1)] for _ in range(m + 1)]  
        
            for i in range(m):
                for j in range(n):        
                    if A[i] == B[j]:
                        dp[i + 1][j + 1] = dp[i][j] + A[i]
                    else:
                        dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1], key=len)
            
            return dp[-1][-1]
        
        ans = ''; i = j = 0
        for x in lcs(str1, str2):
            while str1[i] != x: ans += str1[i]; i += 1
            while str2[j] != x: ans += str2[j]; j += 1
            ans += x; i += 1; j += 1
        return ans + str1[i:] + str2[j:]

class Solution:
    def shortestCommonSupersequence(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        dp = [[''] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if s1[i] == s2[j]:
                    dp[i][j] = dp[i-1][j-1] + s1[i] if i > 0 and j > 0 else s1[i]
                else:
                    if i > 0 and j > 0:
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=lambda x:len(x))
                    elif i > 0:
                        dp[i][j] = dp[i-1][j]
                    elif j > 0:
                        dp[i][j] = dp[i][j-1]
        res, i, j = '', 0, 0
        for ch in dp[-1][-1]:
            while s1[i] != ch:
                res += s1[i]
                i += 1
            while s2[j] != ch:
                res += s2[j]
                j += 1
            res, i, j = res + ch, i + 1, j + 1
        res += s1[i:] + s2[j:]
        return res

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        # Step 1. find a longest common subsequence.
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def helper(i, j): # longest common subseq of str1[:i+1] and str2[:j+1]
            if i < 0 or j < 0:
                return ''
            if str1[i]==str2[j]:
                return helper(i-1, j-1) + str1[i]
            return max(helper(i-1, j), helper(i, j-1), key=len)

        subseq = helper(len(str1)-1, len(str2)-1)
        
        # Step 2. make a supersequences from the longest common subsequence.
        ans, i, j = '', 0, 0
        for c in subseq:
            while str1[i] != c:
                ans += str1[i]; i += 1
            while str2[j] != c:
                ans += str2[j]; j += 1
            ans += c; i += 1; j += 1
        return ans + str1[i:] + str2[j:]                
        
    def shortestCommonSupersequence_dp(self, str1: str, str2: str) -> str:
        if not str1: return str2
        if not str2: return str1
        l1, l2 = len(str1), len(str2)
        # Step 1. find a longest common subsequence.
        dp = [''] * (l1+1)
        for j in range(l2):
            new_dp = dp[:]
            for i in range(l1):
                if str1[i] == str2[j]:
                    new_dp[i+1] = dp[i] + str1[i]
                elif len(dp[i+1]) < len(new_dp[i]):
                    new_dp[i+1] = new_dp[i]
            dp = new_dp
        # Step 2. make a supersequences from the longest common subsequence.
        ans, i, j = '', 0, 0
        for c in dp[-1]:
            while str1[i] != c:
                ans += str1[i]; i += 1
            while str2[j] != c:
                ans += str2[j]; j += 1
            ans += c; i += 1; j += 1
        return ans + str1[i:] + str2[j:]

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m,n = len(str1),len(str2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for x in range(1,m+1):
            for y in range(1,n+1):
                if str1[x-1]==str2[y-1]:
                    dp[x][y] = 1+dp[x-1][y-1]
                else:
                    dp[x][y] = max(dp[x-1][y],dp[x][y-1])
        i,j = m,n
        res = ''
        while(i>0 and j>0):
            if(str1[i-1]==str2[j-1]):
                res=str1[i-1]+res
                i-=1
                j-=1
            elif(dp[i-1][j]==dp[i][j]):
                res = str1[i-1]+res
                i-=1
            else:
                res = str2[j-1]+res
                j-=1
        while(i>0):
            res = str1[i-1]+res
            i-=1
        while(j>0):
            res = str2[j-1]+res
            j-=1
        return res

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        len1 = len(str1)
        len2 = len(str2)
        d = [[10000] * (len2 + 1) for _ in range(len1 + 1)]
        d[0][0] = 0
        for i in range(len1 + 1):
            for j in range(len2 + 1):
                if d[i][j] == 10000:
                    continue
                if i < len1:
                    d[i + 1][j] = min(d[i + 1][j], d[i][j] + 1)
                if j < len2:
                    d[i][j + 1] = min(d[i][j + 1], d[i][j] + 1)
                if i < len1 and j < len2 and str1[i] == str2[j]:
                    d[i + 1][j + 1] = min(d[i + 1][j + 1], d[i][j] + 1)
        pos1 = len1
        pos2 = len2
        ans = []
        while pos1 or pos2:
            while pos1 and pos2 and str1[pos1 - 1] == str2[pos2 - 1]:
                ans.append(str1[pos1 - 1])
                pos1 -= 1
                pos2 -= 1
            while pos1 and d[pos1 - 1][pos2] + 1 == d[pos1][pos2]:
                ans.append(str1[pos1 - 1])
                pos1 -= 1
            while pos2 and d[pos1][pos2 - 1] + 1 == d[pos1][pos2]:
                ans.append(str2[pos2 - 1])
                pos2 -= 1
        ans.reverse()
        return ''.join(ans)



class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        size1, size2 = len(str1), len(str2)
        Inf = str1 + str2
        dp = [None] * (size2 + 1)
        dp[0] = ''
        for i in range(1, size2 + 1):
            dp[i] = dp[i-1] + str2[i-1]
        for i1 in range(1, size1 + 1):
            newDP = [None] * (size2 + 1)
            newDP[0] = dp[0] + str1[i1-1]
            for i2 in range(1, size2 + 1):
                newDP[i2] = Inf
                if str1[i1-1] == str2[i2-1]:
                    newDP[i2] = dp[i2-1] + str1[i1-1]
                newDP[i2] = min(
                    newDP[i2],
                    dp[i2] + str1[i1-1],
                    newDP[i2-1] + str2[i2-1],
                    key=len)
            dp = newDP
        return dp[-1]

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        # Step 1. find a longest common subsequence.
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def helper(i, j): # longest common subseq of str1[:i+1] and str2[:j+1]
            if i == 0:
                if str1[0] == str2[j]:
                    return str1[0]
                elif j == 0:
                    return ''
                else:
                    return helper(i, j-1)
            if j == 0:
                if str1[i] == str2[0]:
                    return str2[0]
                else:
                    return helper(i-1, j)
            # i>0, j>0
            if str1[i]==str2[j]:
                return helper(i-1, j-1) + str1[i]
            else:
                return max(helper(i-1, j), helper(i, j-1), key=len)

        subseq = helper(len(str1)-1, len(str2)-1)
        
        # Step 2. make a supersequences from the longest common subsequence.
        ans, i, j = '', 0, 0
        for c in subseq:
            while i < len(str1) and str1[i] != c:
                ans += str1[i]; i += 1
            while j < len(str2) and str2[j] != c:
                ans += str2[j]; j += 1
            ans += c; i += 1; j += 1
        return ans + str1[i:] + str2[j:]                


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        n = len(str1)
        m = len(str2)
        
        t = [[0 for j in range(m+1)] for i in range(n+1)]
        
        for i in range(1, n+1):
            for j in range(1, m+1):
                if(str1[i-1]==str2[j-1]):
                    t[i][j] = t[i-1][j-1] + 1
                else:
                    t[i][j] = max(t[i-1][j], t[i][j-1])
                    
        s = ''
        
        i, j = n, m
        
        while(i>0 and j>0):
            if(str1[i-1]==str2[j-1]):
                s = s + str1[i-1]
                i-=1
                j-=1
            else:
                if(t[i-1][j]>t[i][j-1]):
                    s = s + str1[i-1]
                    i-=1
                else:
                    s = s + str2[j-1]
                    j-=1
                    
        while(i>0):
            s+=str1[i-1]
            i-=1
        while(j>0):
            s+=str2[j-1]
            j-=1
            
        s = s[::-1]
        
        return s
# class Solution:
#     def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
#         m,n = len(str1), len(str2)
#         dp = [[0 for x in range(n+1)] for y in range(m+1)]
#         for i in range(1,m+1):
#             for j in range(1,n+1):
#                 if str1[i-1] == str2[j-1]:
#                     dp[i][j] = 1+dp[i-1][j-1]
#                 else:
#                     dp[i][j] = max(dp[i-1][j],dp[i][j-1])
#         result = \"\"
#         i,j = m,n
#         while i>0 and j>0:
#             if str1[i-1] == str2[j-1]:
#                 result += str1[i-1]
#                 i -= 1
#                 j -= 1
#             else:
#                 if dp[i][j-1] > dp[i-1][j]:
#                     result += str2[j-1]
#                     j -= 1
#                 elif dp[i-1][j] > dp[i][j-1]:
#                     result += str1[i-1]
#                     i -= 1    
#         while i > 0:
#             result += str1[i-1]
#             i -= 1
#         while j > 0:
#             result += str2[j-1]
#             j -= 1
#         return result[::-1]


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        ## https://www.youtube.com/watch?v=rfV2BJp8YA8 
        ## find longest common subsequence
        m = len(str1)
        n = len(str2)
        dp = [[0 for j in range(n+1)] for i in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = 1+dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    
        # for i in range(m+1):
        #     print(dp[i])
        i = m
        j = n
        res = []
        while i>0 or j>0:
            if i == 0:
                res.append(str2[j-1])
                j -= 1
            elif j == 0:
                res.append(str1[i-1])
                i -= 1
            elif str1[i-1] == str2[j-1]:
                res.append(str1[i-1])
                i -= 1
                j -= 1
            elif dp[i][j] == dp[i-1][j]:
                res.append(str1[i-1])
                i -= 1
            else:
                res.append(str2[j-1])
                j -= 1
            # print(res)
        res.reverse()
        return ''.join(res)
                
        
    
    
# \"cba\"
# \"abc\"


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m = len(str1)
        n = len(str2)
        
        t = str1+str2
        cur = [ '' for _ in range(n+1)]
        prev = [ '' for _ in range(n+1)]
        
        for i in range(m+1):
            for j in range(n+1):
                if i==0:
                    cur[j]=str2[:j]
                elif j==0:
                    cur[j]=str1[:i]
                else:
                    a, b = str1[i-1], str2[j-1]

                    if a==b:
                        cur[j]=prev[j-1]+a
                    else:
                        if len(prev[j])<len(cur[j-1]):
                            cur[j]=prev[j]+a
                        else:
                            cur[j]=cur[j-1]+b
            prev = cur
            cur = [ '' for _ in range(n+1)]
            
                
        
        return prev[-1]
        
        


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        last_dp = [str2[:j] for j in range(len(str2) + 1)]
        
        for i in range(1, len(str1) + 1):
            dp = [str1[:i]]
            for j in range(1, len(str2) + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp.append(last_dp[j - 1] + str1[i - 1])
                else:
                    if len(last_dp[j]) < len(dp[j - 1]):
                        dp.append(last_dp[j] + str1[i - 1])
                    else:
                        dp.append(dp[j - 1] + str2[j - 1])
            last_dp = dp
            
        return last_dp[-1]


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        table = [[[0, -1] for j in range(len(str2))] for i in range(len(str1))]
        if str1[0] == str2[0]:
            table[0][0][0] = 1
        else:
            table[0][0][0] = 2
            table[0][0][1] = 0
        for j in range(1, len(str2)):
            if str1[0] == str2[j]:
                table[0][j][0] = j + 1
                table[0][j][1] = j - 1
            else:
                val1, val2 = j + 1, table[0][j-1][0]
                if val1 < val2:
                    table[0][j][0] = val1 + 1
                    table[0][j][1] = j
                else:
                    table[0][j][0] = val2 + 1
                    table[0][j][1] = j - 1
        for i in range(1, len(str1)):
            if str1[i] == str2[0]:
                table[i][0][0] = i + 1
            else:
                val1, val2 = table[i-1][0][0], i + 1
                if val1 < val2:
                    table[i][0][0] = val1 + 1
                    table[i][0][1] = 0
                else:
                    table[i][0][0] = i + 2
            for j in range(1, len(str2)):
                if str1[i] == str2[j]:
                    table[i][j][0] = table[i-1][j-1][0] + 1
                    table[i][j][1] = j - 1
                else:
                    val1, val2 = table[i-1][j][0], table[i][j-1][0]
                    if val1 < val2:
                        table[i][j][0] = val1 + 1
                        table[i][j][1] = j
                    else:
                        table[i][j][0] = val2 + 1
                        table[i][j][1] = j - 1
        # for j in range(len(str2)):
        #     table[-1][j] += len(str2) - 1 - j        
        # print(table)
        result = ''
        pos1, pos2 = len(str1) - 1, len(str2) - 1
        while True:
            if str1[pos1] == str2[pos2]:
                result = str1[pos1] + result
                pos1, pos2 = pos1 - 1, table[pos1][pos2][1]
            else:
                if table[pos1][pos2][1] == pos2:
                    result = str1[pos1] + result
                    pos1 -= 1
                else:
                    result = str2[pos2] + result
                    pos2 = table[pos1][pos2][1]
            # print(pos1, pos2)  
            if pos1 < 0 or pos2 < 0:
                result = str1[0:pos1+1] + str2[0:pos2+1] + result
                break               
            
        return result                

class Solution:
    def shortestCommonSupersequence(self, a: str, b: str) -> str:
        n, m = len(a), len(b)

        dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]
        def TD(a, b, n, m):
            if dp[n][m] != -1:
                return dp[n][m]
            if n == 0 or m == 0:
                return 0
            if a[n - 1] == b[m - 1]:
                dp[n][m] = 1 + TD(a, b, n - 1, m - 1)
                return dp[n][m]
            dp[n][m] = max(TD(a, b, n - 1, m), TD(a, b, n, m - 1))
            return dp[n][m]
        idx = TD(a, b, n, m)
        lcs = ''
        i = n
        j = m
        while i > 0 and j > 0:
            if a[i - 1] == b[j - 1]:
                lcs+=a[i-1]
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j-1]:
                lcs+=a[i-1]
                i -= 1
            else:
                lcs+=b[j-1]
                j -= 1
        while i > 0:
            lcs += a[i - 1]
            i -= 1
        while j > 0:
            lcs += b[j - 1]
            j -= 1
        lcs = lcs[::-1]
        return lcs

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        n1 = len(str1)
        n2 = len(str2)
        
        dp = [['']*(n2+1) for _ in range(n1+1)]
        for i in range(1,n1+1):
            for j in range(1,n2+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + str1[i-1]
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1], key=len)
        lcs = dp[-1][-1]
        
        i = j = 0
        res = ''
        for ch in lcs:
            while str1[i] != ch:
                res += str1[i]
                i += 1
            while str2[j] != ch:
                res += str2[j]
                j += 1
            res += ch
            i+=1
            j+=1
        return res+str1[i:]+str2[j:]
            


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m = len(str1)
        n = len(str2)
        
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(m):
            dp[i + 1][0] = dp[i][0] + 1
            
        for i in range(n):
            dp[0][i + 1] = dp[0][i] + 1
        
        for i in range(m):
            for j in range(n):
                if str1[i] == str2[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j]) + 1
        
        ans = []
        
        i = m
        j = n
        while i > 0 or j > 0:
            if i > 0 and j > 0 and str1[i - 1] == str2[j - 1]:
                i -= 1
                j -= 1
                ans.append(str1[i])
            elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
                i -= 1
                ans.append(str1[i])
            elif j > 0 and dp[i][j] == dp[i][j - 1] + 1:
                j -= 1
                ans.append(str2[j])
        return ''.join(ans[::-1])

from functools import lru_cache

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        @lru_cache(None)
        def dfs(i1, i2):
            if i1 == m or i2 == n:
                return ''
            if str1[i1] == str2[i2]:
                return str1[i1] + dfs(i1 + 1, i2 + 1)
            x, y = dfs(i1 + 1, i2), dfs(i1, i2 + 1)
            if len(x) > len(y):
                return x
            else:
                return y
        
        res = dfs(0, 0)
        ans, idx1, idx2 = '', 0, 0
        for c in res:
            while idx1 < m and str1[idx1] != c:
                ans += str1[idx1]
                idx1 += 1
            while idx2 < n and str2[idx2] != c:
                ans += str2[idx2]
                idx2 += 1
            ans += c
            idx1 += 1
            idx2 += 1
        ans += str1[idx1:]
        ans += str2[idx2:]
        return ans
        


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        n1 = len(str1)
        n2 = len(str2)
        
        dp = [['']*(n2+1) for _ in range(n1+1)]
        for i in range(1,n1+1):
            for j in range(1,n2+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + str1[i-1]
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1], key=len)
        lcs = dp[-1][-1]
        
        i = j = 0
        res = []
        for ch in lcs:
            while str1[i] != ch:
                res.append(str1[i])
                i += 1
            while str2[j] != ch:
                res.append(str2[j])
                j += 1
            res.append(ch)
            i+=1
            j+=1
        return ''.join(res)+str1[i:]+str2[j:]


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        d = [[10000] * (len(str2) + 1) for _ in range(len(str1) + 1)]
        d[0][0] = 0
        for i in range(len(str1) + 1):
            for j in range(len(str2) + 1):
                if d[i][j] == 10000:
                    continue
                if i < len(str1):
                    d[i + 1][j] = min(d[i + 1][j], d[i][j] + 1)
                if j < len(str2):
                    d[i][j + 1] = min(d[i][j + 1], d[i][j] + 1)
                if i < len(str1) and j < len(str2) and str1[i] == str2[j]:
                    d[i + 1][j + 1] = min(d[i + 1][j + 1], d[i][j] + 1)
        pos1 = len(str1)
        pos2 = len(str2)
        ans = []
        while pos1 or pos2:
            if pos1 and d[pos1 - 1][pos2] + 1 == d[pos1][pos2]:
                ans.append(str1[pos1 - 1])
                pos1 -= 1
                continue
            if pos2 and d[pos1][pos2 - 1] + 1 == d[pos1][pos2]:
                ans.append(str2[pos2 - 1])
                pos2 -= 1
                continue
            if pos1 and pos2 and str1[pos1 - 1] == str2[pos2 - 1]:
                ans.append(str1[pos1 - 1])
                pos1 -= 1
                pos2 -= 1
                continue
        ans.reverse()
        return ''.join(ans)




class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        
        def lcs(text1, text2):
            m = len(text1)
            n = len(text2)
            dp = [['']*(n+1) for _ in range(m+1)]
            for i in range(1, m+1):
                for j in range(1, n+1):
                    if text1[i-1]==text2[j-1]:
                        dp[i][j] = dp[i-1][j-1] + text1[i-1]
                    else:
                        dp[i][j] = max(dp[i][j-1], dp[i-1][j], key=lambda x: len(x))
            return dp[-1][-1]
        
        if str1==str2:
            return str1
        i = 0
        j = 0
        ans = ''
        for c in lcs(str1, str2):
            while str1[i]!=c:
                ans += str1[i]
                i += 1
            while str2[j]!=c:
                ans += str2[j]
                j += 1
            ans += c
            i += 1
            j += 1
        return ans + str1[i:] + str2[j:]

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        n1, n2 = len(str1), len(str2)
        dp = [[0 for j in range(n2+1)] for i in range(n1+1)]
        for i in range(1, n1+1):
            for j in range(1, n2+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        i, j, ans = n1-1, n2-1, ''
        while i >= 0 and j >= 0:
            if dp[i+1][j+1] == dp[i][j+1]:
                ans = str1[i] + ans
                i -= 1
            elif dp[i+1][j+1] == dp[i+1][j]:
                ans = str2[j] + ans
                j -= 1
            else:
                ans = str1[i] + ans
                i -= 1
                j -= 1
        if i < 0:
            ans = str2[:j+1] + ans
        else:
            ans = str1[:i+1] + ans
        return ans
            
            
        


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        
        step = defaultdict(lambda : None)
        
        @lru_cache(None)
        def cal(i, j):
            if i >= len(str1):
                return len(str2)-j
            if j >= len(str2):
                return len(str1)-i
            
            if str1[i] == str2[j]:
                step[(i, j)] = 0
                return 1 + cal(i+1, j+1)
            else:
                a = cal(i+1, j)
                b = cal(i, j+1)
                if a < b:
                    step[(i, j)] = 1
                    return 1 + a
                else:
                    step[(i, j)] = 2
                    return 1 + b
        cal(0, 0)
        
        ans = []
        
        def cons(i, j):
            nonlocal ans  
            if i>=len(str1):
                ans.append(str2[j:])
                return 
            if j>=len(str2):
                ans.append(str1[i:])
                return
            s = step[(i, j)]
            if s == 0:
                ans.append(str1[i])
                i+=1
                j+=1
            elif s == 1:
                ans.append(str1[i])
                i+=1
            else:
                ans.append(str2[j])
                j+=1
            cons(i, j)
        cons(0, 0)
        return ''.join(ans)

class Solution:
    def shortestCommonSupersequence(self, s1: str, s2: str) -> str:
        m = {}
        def fs(a, b):
            if (a, b) in list(m.keys()):
                return m[(a, b)]
            if a == len(s1) or b == len(s2):
                m[(a, b)] = ''
                return ''
            if s1[a] == s2[b]:
                r = s1[a] + fs(a + 1, b + 1)
                return r
            r1 = fs(a + 1, b)
            r2 = fs(a, b + 1)
            if len(r1) > len(r2):
                m[(a, b)] = r1
            else:
                m[(a, b)] = r2
            return m[(a, b)]
        r = fs(0, 0)
        res = ''
        i, j = 0, 0
        for a in r:
            while i < len(s1) and s1[i] != a:
                res += s1[i]
                i += 1
            i += 1
            while j < len(s2) and s2[j] != a:
                res += s2[j]
                j += 1
            j += 1
            res += a
        res += s1[i:] + s2[j:]
        return res
        
        


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m = len(str1)
        n = len(str2)
        
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(m):
            dp[i + 1][0] = dp[i][0] + 1
            
        for i in range(n):
            dp[0][i + 1] = dp[0][i] + 1
        
        for i in range(m):
            for j in range(n):
                if str1[i] == str2[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j]) + 1
        
        ans = []
        
        i = m
        j = n
        while i > 0 or j > 0:
            if i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1 and str1[i - 1] == str2[j - 1]:
                i -= 1
                j -= 1
                ans.append(str1[i])
            elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
                i -= 1
                ans.append(str1[i])
            elif j > 0 and dp[i][j] == dp[i][j - 1] + 1:
                j -= 1
                ans.append(str2[j])
        return ''.join(ans[::-1])

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m = len(str1)
        n = len(str2)        
        dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
        
        for i in range(1, m + 1):
            dp[i][0] = i
        
        for j in range(1, n + 1):
            dp[0][j] = j
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
        
        ans = ''
        i, j = m, n
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                ans += str1[i - 1]
                i -= 1
                j -= 1
            elif dp[i][j] == dp[i - 1][j] + 1:
                ans += str1[i - 1]
                i -= 1
            elif dp[i][j] == dp[i][j - 1] + 1:
                ans += str2[j - 1]
                j -= 1
        
        while i > 0:
            ans += str1[i - 1]
            i -= 1
        
        while j > 0:
            ans += str2[j - 1]
            j -= 1
        
        return ans[::-1]


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        if not str1: return str2
        if not str2: return str1
        l1, l2 = len(str1), len(str2)
        # Step 1. find a longest common subsequence.
        dp = [''] * (l1+1)
        for j in range(l2):
            new_dp = dp[:]
            for i in range(l1):
                if str1[i] == str2[j]:
                    new_dp[i+1] = dp[i] + str1[i]
                elif len(dp[i+1]) < len(new_dp[i]):
                    new_dp[i+1] = new_dp[i]
            dp = new_dp
        # Step 2. make a supersequences from the longest common subsequence.
        ans, i, j = '', 0, 0
        for c in dp[-1]:
            while str1[i] != c:
                ans += str1[i]; i += 1
            while str2[j] != c:
                ans += str2[j]; j += 1
            ans += c; i += 1; j += 1
        return ans + str1[i:] + str2[j:]

class Solution:
    def shortestCommonSupersequence(self, a: str, b: str) -> str:
        n=len(a)
        m=len(b)
        dp=[['-1']*(n+1) for i in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if(i==0 or j==0):
                    dp[i][j]=''
                else:
                    if(a[j-1]==b[i-1]):
                        dp[i][j]=a[j-1]+dp[i-1][j-1]
                    else:
                        s1=dp[i-1][j]
                        s2=dp[i][j-1]
                        if(len(s1)>len(s2)):
                            dp[i][j]=s1
                        else:
                            dp[i][j]=s2
        s=dp[-1][-1][::-1]
        result=''
        I=0
        J=0
        for i in s:
            while(a[I]!=i):
                result=result+a[I]
                I=I+1
            while(b[J]!=i):
                result=result+b[J]
                J=J+1
            result=result+i
            I=I+1
            J=J+1

        return(result+a[I:]+b[J:])

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n  = len(str1), len(str2)
        dp = [[''] * (n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + str1[i-1]
                else:
                    dp[i][j] = dp[i-1][j] if len(dp[i-1][j]) > len(dp[i][j-1]) else dp[i][j-1]
                    
        lcs = dp[-1][-1]
        
        res, i, j = '', 0, 0
        print(lcs)
        for c in lcs:
            while str1[i] != c:
                res += str1[i]
                i+=1
            while str2[j] != c:
                res += str2[j]
                j+=1
            res += c
            i, j = i+1, j+1
        return res + str1[i:] + str2[j:]

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m = len(str1)
        n = len(str2)
        DP = [[0 for j in range(n + 1)] for i in range(m + 1)]
        res = []
        
        for i in range(m + 1):
            DP[i][0] = i
        for j in range(n + 1):
            DP[0][j] = j
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    DP[i][j] = 1 + DP[i - 1][j - 1]
                else:
                    if DP[i - 1][j] < DP[i][j - 1]:
                        DP[i][j] = 1 + DP[i - 1][j]
                    else:
                        DP[i][j] = 1 + DP[i][j - 1]
        #print(DP[m][n])
        #build string from DP array
        i = m
        j = n
        res = []
        while i > 0 or j > 0:
            if i - 1 >= 0 and j - 1 >= 0 and str1[i - 1] == str2[j - 1]:
                res.append(str1[i - 1])
                i -= 1
                j -= 1
            else:
                if DP[i - 1][j] < DP[i][j - 1]:
                    res.append(str1[i - 1])
                    i -= 1
                else:
                    res.append(str2[j - 1])
                    j -= 1
        return ''.join(reversed(res))

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        cache = [[0 for i in range(len(str2)+1)] for j in range(len(str1)+1)]
        for i in range(1, len(str1)+1):
            for j in range(1, len(str2)+1):
                if str1[i-1] == str2[j-1]:
                    cache[i][j] = 1+cache[i-1][j-1]
                else:
                    cache[i][j] = max(cache[i][j-1], cache[i-1][j])
        print(cache)
        i,j = len(str1), len(str2)
        ans = ''
        while i>0 and j>0:
            if str1[i-1] == str2[j-1]:
                ans = str1[i-1] + ans
                i -= 1
                j -= 1
            elif cache[i][j-1] > cache[i-1][j]:
                ans = str2[j-1] + ans
                j -= 1
            else:
                ans = str1[i-1]+ans
                i -= 1
        print(str1, str2, ans, i, j)
        if i > 0:
            ans = str1[:i] + ans
            i -= 1
        if j > 0:
            ans = str2[:j] + ans
            j -= 1
        return ans

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        
        #https://leetcode.com/problems/shortest-common-supersequence/discuss/639784/Python-DP-with-detailed-explanation
        #https://leetcode.com/problems/shortest-common-supersequence/discuss/674175/Python-Very-simple-solution-with-DP-Table-Memory-95
        
        m,n = len(str1)+1, len(str2)+1
        dp = ['']*n
        for c in range(n):
            dp[c] = str2[:c]
        for r in range(1, m):
            pre = dp[:]    #use pre to store last row's information
            dp[0] += str1[r-1]
            for c in range(1, n):
                if str1[r-1] == str2[c-1]:
                    dp[c] = pre[c-1]+str1[r-1]
                else:
                    if len(pre[c]) < len(dp[c-1]):
                        dp[c] = pre[c] + str1[r-1]
                    else:
                        dp[c] = dp[c-1] + str2[c-1]
        return dp[-1]

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        n = len(str1)
        m = len(str2)
        
        dp = [[-1] * (m + 1) for _ in range(n + 1)]
        
        for i in range(n + 1):
            for j in range(m + 1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                else:
                    if str1[i - 1] == str2[j - 1]:
                        dp[i][j] = 1 + dp[i - 1][j - 1]
                    else:
                        dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
        
        i = n
        j = j
        result = []
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                result.append(str1[i - 1])
                i -= 1
                j -= 1
            else:
                left = dp[i][j - 1]
                top = dp[i - 1][j]
                if left > top:
                    result.append(str2[j - 1])
                    j -= 1
                else:
                    result.append(str1[i - 1])
                    i -= 1
        
        while i > 0:
            result.append(str1[i - 1])
            i -= 1
        while j > 0:
            result.append(str2[j - 1])
            j -= 1
        
        result = ''.join(result[::-1])
        return result
                


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        str1 = '0' + str1
        str2 = '0' + str2
        len_1, len_2 = len(str1), len(str2)
        
        dp = [[0] * len_2 for _ in range(len_1)]
        
        for i in range(1, len_1):
            for j in range(1, len_2):
                if str1[i] == str2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        
        res = ''
        m, n = len_1 - 1, len_2 - 1
        while m > 0 or n > 0:
            if m == 0:
                res += str2[n]
                n -= 1
            elif n == 0:
                res += str1[m]
                m -= 1
            elif str1[m] == str2[n]:
                res += str1[m]
                m -= 1
                n -= 1
            elif dp[m-1][n] == dp[m][n]:
                res += str1[m]
                m -= 1
            elif dp[m][n-1] == dp[m][n]:
                res += str2[n]
                n -= 1
        # print(res)
        return res[::-1]


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        n = len(str1)
        m = len(str2)
        
        dp = [[-1] * (m + 1) for _ in range(n + 1)]
        
        for i in range(n + 1):
            for j in range(m + 1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                else:
                    if str1[i - 1] == str2[j - 1]:
                        dp[i][j] = 1 + dp[i - 1][j - 1]
                    else:
                        dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
        
        i = n
        j = m
        result = []
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                result.append(str1[i - 1])
                i -= 1
                j -= 1
            else:
                left = dp[i][j - 1]
                top = dp[i - 1][j]
                if left > top:
                    result.append(str2[j - 1])
                    j -= 1
                else:
                    result.append(str1[i - 1])
                    i -= 1
        
        while i > 0:
            result.append(str1[i - 1])
            i -= 1
        while j > 0:
            result.append(str2[j - 1])
            j -= 1
        
        result = ''.join(result[::-1])
        return result
                


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        longest_common_sub = ''
        str1_len = len(str1)
        str2_len = len(str2)
        dp = [[0 for _ in range(str2_len + 1)] for _ in range(str1_len + 1)]
        for i in range(str1_len + 1):
            dp[i][0] = i
        for j in range(str2_len + 1):
            dp[0][j] = j
        for i in range(1,str1_len+1):
            for j in range(1, str2_len+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
        # reconstruct the array
        toret = []
        i = str1_len
        j = str2_len
        while i > 0 or j > 0:
            if i > 0 and j > 0 and str1[i-1] == str2[j-1]:
                toret.append(str1[i-1])
                i -= 1
                j -= 1
            else:
                if dp[i-1][j] < dp[i][j-1]:
                    toret.append(str1[i-1])
                    i -= 1
                else:
                    toret.append(str2[j-1])
                    j -= 1
        return ''.join(reversed(toret))


class Solution:
    def shortestCommonSupersequence(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i, c in enumerate(s1):
            for j, d in enumerate(s2):
                dp[i + 1][j + 1] = 1 + dp[i][j] if c == d else max(dp[i + 1][j], dp[i][j + 1])
        i, j, stk = m - 1, n - 1, []
        while i >= 0 and j >= 0:
            if s1[i] == s2[j]:
                stk.append(s1[i])
                i -= 1
                j -= 1
            elif dp[i + 1][j] < dp[i][j + 1]:
                stk.append(s1[i])
                i -= 1
            else:
                stk.append(s2[j])
                j -= 1    
        return s1[: i + 1] + s2[: j + 1] + ''.join(reversed(stk))

class Solution:
    def shortestCommonSupersequence(self, s: str, t: str) -> str:
        dp =[[-1 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
        
        for i in range(len(s)+1):
            for j in range(len(t)+1):
                if i==0 or j==0:
                    dp[i][j]=0
                elif s[i-1]==t[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        # for i in dp:
        #     print(i)
        lcs =''
        i,j=len(s),len(t)
        while i>0 and j>0:
            if s[i-1]==t[j-1]:
                lcs += s[i-1]
                i-=1
                j-=1
            else:
                if dp[i][j-1]>dp[i-1][j]:
                    j-=1
                    lcs += t[j]
                else:
                    i-=1
                    lcs+=s[i]
        while i>0:
            i-=1
            lcs+=s[i]
        while j>0:
            j-=1
            lcs +=t[j]
        return lcs[::-1]

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        M, N = len(str1), len(str2)
        
        dp = [['']*(N+1) for _ in range(M+1)]
        
        ## TLE...
#         for i in range(M):
#             dp[i+1][0] = str1[:i+1]
#         for i in range(N):
#             dp[0][i+1] = str2[:i+1]
        
#         for i in range(1, M+1):
#             for j in range(1, N+1):
#                 if str1[i-1]==str2[j-1]:
#                     dp[i][j] = dp[i-1][j-1] + str1[i-1]
#                 else:
#                     if len(dp[i][j-1]) < len(dp[i-1][j]):
#                         dp[i][j] = dp[i][j-1] + str2[j-1]
#                     else:
#                         dp[i][j] = dp[i-1][j] + str1[i-1]
#                     # dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1
        
#         return dp[M][N]
        
        for i in range(1, M+1):
            for j in range(1, N+1):
                if str1[i-1]==str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + str1[i-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=len)
        LCS = dp[M][N]
        
        res = ''
        i = j = 0
        for c in LCS:
            while str1[i]!=c:
                res += str1[i]
                i+=1
            while str2[j]!=c:
                res += str2[j]
                j+=1
            res += c
            i+=1
            j+=1
        res += str1[i:]
        res += str2[j:]
        
        return res

class Solution:
    def shortestCommonSupersequence(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        dp = [[''] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if s1[i] == s2[j]:
                    dp[i][j] = dp[i-1][j-1] + s1[i] if i > 0 and j > 0 else s1[i]
                else:
                    if i > 0 and j > 0:
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=len)
                    elif i > 0:
                        dp[i][j] = dp[i-1][j]
                    elif j > 0:
                        dp[i][j] = dp[i][j-1]
        res, i, j = '', 0, 0
        for ch in dp[-1][-1]:
            while s1[i] != ch:
                res += s1[i]
                i += 1
            while s2[j] != ch:
                res += s2[j]
                j += 1
            res, i, j = res + ch, i + 1, j + 1
        res += s1[i:] + s2[j:]
        return res

class Solution:
    def shortestCommonSupersequence(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i, c in enumerate(s1):
            for j, d in enumerate(s2):
                dp[i + 1][j + 1] = 1 + dp[i][j] if c == d else max(dp[i + 1][j], dp[i][j + 1])
        i, j, stk = m - 1, n - 1, []
        while i >= 0 and j >= 0:
            if s1[i] == s2[j]:
                stk.append(s1[i])
                i -= 1
                j -= 1
            elif dp[i + 1][j] < dp[i][j + 1]:
                stk.append(s1[i])
                i -= 1
            else:
                stk.append(s2[j])
                j -= 1 
        return s1[: i + 1] + s2[: j + 1] + ''.join(reversed(stk))

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        n1, n2 = len(str1), len(str2)
        def lcs():
            dp = [[''] * (n2 + 1) for _ in range(n1 + 1)]
            for i in range(1, n1 + 1):
                for j in range(1, n2 + 1):
                    if str1[i-1] == str2[j-1]:
                        dp[i][j] = dp[i-1][j-1] + str1[i-1]
                    else:
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=len)
            return dp[-1][-1]
            
            
        i = j = 0
        res = ''
        for ch in lcs():
            while i < n1 and str1[i] != ch:
                res += str1[i]
                i += 1
            while j < n2 and str2[j] != ch:
                res += str2[j]
                j += 1
            res += ch
            i += 1
            j += 1
        return res + str1[i:] + str2[j:]


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        
        
        @lru_cache(None)
        def lcs(x, y):
            
            m, n = len(x), len(y)
            
            dp = [['' for _ in range(n+1)] for _ in range(m+1)]
            
            for i in range(1, m+1):
                for j in range(1, n+1):
                    if x[i-1] == y[j-1]:
                        dp[i][j] = dp[i-1][j-1] + x[i-1]
                    else:
                        dp[i][j] = max(dp[i][j-1], dp[i-1][j], key=len)
                        
            return dp[-1][-1]

            
        # print(lcs(str1, str2))
        lcs_ = lcs(str1, str2)
        
        
        i = 0 
        j = 0
        res = ''
        for c in lcs_:
            while str1[i] != c:
                res += str1[i]
                i += 1
            while str2[j] != c:
                res += str2[j] 
                j += 1
                
            res += c
            i += 1
            j += 1
            
        # print(res)
        
        return res + str1[i:] + str2[j:]
            
            


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        # build dp for LCS
        dp = [[0]*(len(str1)+1) for _ in range(len(str2)+1)]
        
        for r in range(1, len(dp)):
            for c in range(1, len(dp[0])):
                diag = dp[r-1][c-1]
                up = dp[r-1][c]
                left = dp[r][c-1]
                if str1[c-1] == str2[r-1]:
                    diag += 1
                dp[r][c] = max(diag, up, left)
        
        # build supersequence by going up the dp grid
        r = len(str2)
        c = len(str1)
        res = []
        while r > 0 and c > 0:
            if str1[c-1] == str2[r-1]:
                res.append(str1[c-1])
                r -= 1
                c -= 1
            else:
                # move up/left depending on which dp is larger
                up = dp[r-1][c]
                left = dp[r][c-1]
                if up > left:
                    # move up
                    res.append(str2[r-1])
                    r -= 1
                else:
                    # move left
                    res.append(str1[c-1])
                    c -= 1
        
        while r > 0:
            res.append(str2[r-1])
            r -= 1
        
        while c > 0:
            res.append(str1[c-1])
            c -= 1
        
        return ''.join(res[::-1])

class Solution:
   
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        if len(str2) > len(str1):
            str1, str2 = str2, str1
        if not str1 or not str2:
            return str1
        m, n = len(str1), len(str2)
        dp = [[0] * (m+1) for _ in range(n+1)]
        
        for i in range(1, n+1):
            for j in range(1, m+1):
                if str2[i-1] == str1[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        #print(dp)
        final_str = ''
        i, j = n, m
        c1 = str1[j-1]
        c2 = str2[i-1]
        while i > 0 or j > 0:
            #print(f'{i} {c2} {j} {c1}')
            if c1 == c2:
                final_str += c1
                i -= 1
                j -= 1
                c1 = str1[j-1] if j > 0 else ''
                c2 = str2[i-1] if i > 0 else ''
            else:
                if i == 0 or dp[i][j-1] > dp[i-1][j]:
                    final_str += c1
                    j -= 1
                    c1 = str1[j-1] if j > 0 else ''
                else:
                    final_str += c2
                    i -= 1
                    c2 = str2[i-1] if i > 0 else ''
        return ''.join(reversed(final_str))
                    



class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m = len(str1)
        n = len(str2)
        dp = [[-1]*(n+1) for i in range(m+1)]
        for i in range(m+1):
            dp[i][0]=0
        for j in range(n+1):
            dp[0][j]=0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if str1[i-1]==str2[j-1]:
                    dp[i][j]=1+dp[i-1][j-1]
                else:
                    dp[i][j]=max(dp[i-1][j], dp[i][j-1])
        i = m
        j = n
        s = ''
        while(i>0 and j>0):
            if str1[i-1]==str2[j-1]:
                s = s+str1[i-1]
                i = i-1
                j = j-1
            else:
                if dp[i-1][j]>dp[i][j-1]:
                    s = s+str1[i-1]
                    i = i-1
                else:
                    s=s+str2[j-1]
                    j = j-1
        while(i>0):
            s = s+str1[i-1]
            i = i-1
        while(j>0):
            s= s+str2[j-1]
            j = j-1
        return s[::-1]

class Solution:
    def shortestCommonSupersequence(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        dp = [[''] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if s1[i] == s2[j]:
                    dp[i][j] = dp[i-1][j-1] + s1[i] if i > 0 and j > 0 else s1[i]
                else:
                    if i > 0 and j > 0:
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=len)
                    elif i > 0:
                        dp[i][j] = dp[i-1][j]
                    elif j > 0:
                        dp[i][j] = dp[i][j-1]

        res, i, j = '', 0, 0
        for ch in dp[-1][-1]:
            while i < len(s1) and s1[i] != ch:
                res += s1[i]
                i += 1
            while j < len(s2) and s2[j] != ch:
                res += s2[j]
                j += 1
            res += ch
            i += 1
            j += 1
        res += s1[i:] + s2[j:]
        return res

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        '''
        @params: two strings str1 and str2
        @return: shortest common supersequence
        '''
        # Use Dynamic Programming to first compute shortest common subsequence
        m = len(str1)
        n = len(str2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        
        for i in range(1, m+1):
            for j in range(1, n+1):
                # Case 1: delete text1[i] in common subsequence
                deletion = dp[i-1][j]
                # Case 2: delete text2[j] in common subsequence
                insertion = dp[i][j-1]
                # Case 3: match --> common subsequence extend by 1
                match = dp[i-1][j-1] + 1
                # Case 4: mistch --> common subsequence keeps the same
                mismatch = dp[i-1][j-1]
                
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = max(deletion, insertion, match)
                else:
                    dp[i][j] = max(deletion, insertion, mismatch)
                    
        # Backtrack from dp[m][n] to construct shortest common supersequence
        # in revered order
        i, j = m, n
        ans = []
        
        while i > 0 or j > 0:
            # Case 1: str1 is used up
            if i == 0:
                ans.append(str2[j-1])
                j -= 1
                
            # Case 2: str2 is used up
            elif j == 0:
                ans.append(str1[i-1])
                i -= 1
            
            # Case 3: match
            elif str1[i-1] == str2[j-1]:
                ans.append(str1[i-1])
                i -= 1
                j -= 1
                
            # Case 4: insertion of str1
            elif dp[i][j] == dp[i-1][j]:
                ans.append(str1[i-1])
                i -= 1
                
            # Case 5: deletion of str2
            elif dp[i][j] == dp[i][j-1]:
                ans.append(str2[j-1])
                j -= 1
            
            #print('i, j: ', i, j)
            #print(''.join(reversed(ans)))
        
        return ''.join(reversed(ans))
            


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        s = []
        i, j = m, n
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                s.append(str1[i - 1])
                i -= 1
                j -= 1
            elif dp[i][j - 1] > dp[i - 1][j]:
                s.append(str2[j - 1])
                j -= 1
            else:
                s.append(str1[i - 1])
                i -= 1
        while j > 0:
            s.append(str2[j - 1])
            j -= 1
        while i > 0:
            s.append(str1[i - 1])
            i -= 1
        s.reverse()
        return ''.join(s)

class Solution:
    def shortestCommonSupersequence(self, a: str, b: str) -> str:
        def lcs(a,b):
            n, m = len(a),len(b)
            dp = [['' for j in range(m+1)] for i in range(n+1)]
            for i in range(n):
                for j in range(m):
                    if a[i]==b[j]:
                        dp[i+1][j+1]=dp[i][j]+a[i]
                    else:
                        dp[i+1][j+1]=max(dp[i+1][j], dp[i][j+1] , key =len)
            return dp[-1][-1]
        res , i ,j = '',0,0
        for c in lcs(a,b):
            while a[i]!=c:
                res+=a[i]
                i+=1
            while b[j]!=c:
                res+=b[j]
                j+=1
            res+=c
            i+=1
            j+=1
        res+= a[i:]+b[j:]
        return res

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m=len(str1)
        n=len(str2)
        
        dp = [[0 for x in range(n+1)] for x in range(m+1)] 
  
        for i in range(m+1): 
            for j in range(n+1): 
                if i == 0 or j == 0: 
                    dp[i][j] = 0
                elif str1[i-1] == str2[j-1]: 
                    dp[i][j] = dp[i-1][j-1] + 1
                else: 
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
        s=''
        i = m
        j = n
        while i > 0 and j > 0:
            if str1[i-1] == str2[j-1]: 
                s += str1[i-1] 
                i-=1
                j-=1
  
            elif dp[i-1][j] > dp[i][j-1]:
                i-=1
            else: 
                j-=1
        res=s[::-1]
        i,j,st=0,0,0
        final=''
        while(i<m and j<n and st<len(res)):
            if str1[i]!=res[st]:
                final+=str1[i]
                i+=1
            if str2[j]!=res[st]:
                final+=str2[j]
                j+=1
            elif str1[i]==res[st]:
                final+=res[st]
                i+=1
                j+=1
                st+=1
        final+=str2[j:]+str1[i:]
            
        return final

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        size1, size2 = len(str1), len(str2)
        dp = [None] * (size2 + 1)
        dp[0] = ''
        for i in range(1, size2 + 1):
            dp[i] = dp[i-1] + str2[i-1]
        for i1 in range(1, size1 + 1):
            newDP = [None] * (size2 + 1)
            newDP[0] = dp[0] + str1[i1-1]
            for i2 in range(1, size2 + 1):
                if str1[i1-1] == str2[i2-1]:
                    newDP[i2] = dp[i2-1] + str1[i1-1]
                else:
                    newDP[i2] = min(
                        dp[i2] + str1[i1-1],
                        newDP[i2-1] + str2[i2-1],
                        key=len)
            dp = newDP
        return dp[-1]

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        size1, size2 = len(str1), len(str2)
        Inf = str1 + str2
        dp = [None] * (size2 + 1)
        dp[0] = ''
        for i in range(1, size2 + 1):
            dp[i] = dp[i-1] + str2[i-1]
        for i1 in range(1, size1 + 1):
            newDP = [None] * (size2 + 1)
            newDP[0] = dp[0] + str1[i1-1]
            for i2 in range(1, size2 + 1):
                if str1[i1-1] == str2[i2-1]:
                    newDP[i2] = dp[i2-1] + str1[i1-1]
                else:
                    newDP[i2] = min(
                        dp[i2] + str1[i1-1],
                        newDP[i2-1] + str2[i2-1],
                        key=len)
            dp = newDP
        return dp[-1]

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        
        for i in range(1, m+1):
            for j in range(1, n+1):
                if str1[i-1]==str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        i, j = m, n
        lcs = []
        
        while i>0 and j>0:
            if str1[i-1]==str2[j-1]:
                lcs.append(str1[i-1])
                i -= 1
                j -= 1
            else:
                if dp[i-1][j]>dp[i][j-1]:
                    i -= 1
                else:
                    j -= 1
        
        lcs.reverse()
        insert_1 = defaultdict(list)
        idx = 0
        
        for i in range(m):
            if idx<len(lcs) and str1[i]==lcs[idx]:
                idx += 1
            else:
                insert_1[idx].append(str1[i])
        
        insert_2 = defaultdict(list)
        idx = 0
        
        for i in range(n):
            if idx<len(lcs) and str2[i]==lcs[idx]:
                idx += 1
            else:
                insert_2[idx].append(str2[i])

        ans = ''
        
        for i in range(idx):
            ans += ''.join(insert_1[i])+''.join(insert_2[i])+lcs[i]
        
        ans += ''.join(insert_1[idx])+''.join(insert_2[idx])
        return ans
            


class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        @lru_cache(None)
        def dp(i, j):
            if i == m or j == n:
                return 0
            if str1[i] == str2[j]:
                return 1 + dp(i + 1, j + 1)
            return max(dp(i + 1, j), dp(i, j + 1))
        dp(0, 0)
        i = 0
        j = 0
        result = ''
        while i < m and j < n:
            if str1[i] == str2[j]:
                result += str1[i]
                i += 1
                j += 1
            else:
                s1 = dp(i + 1, j)
                s2 = dp(i, j + 1)
                if s1 > s2:
                    result += str1[i]
                    i += 1
                else:
                    result += str2[j]
                    j += 1
        if i < m:
            result += str1[i:]
        if j < n:
            result += str2[j:]
        return result