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: MEDIUM
Tags: String algorithms

Dynamic programming
Skill types: Dynamic programming

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:]
	elif 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']
				elif str2[i] == str1[k]:
					matrix[i][k] = [matrix[i - 1][k - 1][0] + 1, 'D']
				elif 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
		str_val = str_val[::-1]
		str1_lis = str1_lis[::-1]
		str2_lis = str2_lis[::-1]
		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)
			elif (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]
				elif 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:
		from functools import lru_cache

		@lru_cache(maxsize=None)
		def helper(i, j):
			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)
		(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))
		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
		(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:
		(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:
		from functools import lru_cache

		@lru_cache(maxsize=None)
		def helper(i, j):
			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)
			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)
		(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
			elif 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 = 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])
		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
		res.reverse()
		return ''.join(res)


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
					elif 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])
				elif 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
		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])
			elif table[pos1][pos2][1] == pos2:
				result = str1[pos1] + result
				pos1 -= 1
			else:
				result = str2[pos2] + result
				pos2 = table[pos1][pos2][1]
			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:

		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:
		if not str1:
			return str2
		if not str2:
			return str1
		(l1, l2) = (len(str1), len(str2))
		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
		(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] = ''
				elif 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]
				elif 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]
		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
			elif 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:
		(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[:]
			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]
				elif 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
				elif 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
		return res[::-1]


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
		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
			elif 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])
		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
			elif 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)]
		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, 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]
		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
		return res + str1[i:] + str2[j:]


class Solution:

	def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
		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)
		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:
				up = dp[r - 1][c]
				left = dp[r][c - 1]
				if up > left:
					res.append(str2[r - 1])
					r -= 1
				else:
					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])
		final_str = ''
		(i, j) = (n, m)
		c1 = str1[j - 1]
		c2 = str2[i - 1]
		while i > 0 or j > 0:
			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 ''
			elif 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 = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				deletion = dp[i - 1][j]
				insertion = dp[i][j - 1]
				match = dp[i - 1][j - 1] + 1
				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)
		(i, j) = (m, n)
		ans = []
		while i > 0 or j > 0:
			if i == 0:
				ans.append(str2[j - 1])
				j -= 1
			elif j == 0:
				ans.append(str1[i - 1])
				i -= 1
			elif str1[i - 1] == str2[j - 1]:
				ans.append(str1[i - 1])
				i -= 1
				j -= 1
			elif dp[i][j] == dp[i - 1][j]:
				ans.append(str1[i - 1])
				i -= 1
			elif dp[i][j] == dp[i][j - 1]:
				ans.append(str2[j - 1])
				j -= 1
		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:
		(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
			elif 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