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:**

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.

**Constraints**:

`1 <= str1.length, str2.length <= 1000`

`str1`

and`str2`

consist of lowercase English letters.

## Solution:

```
class Solution(object):
def shortestCommonSupersequence(str1, str2):
def lcs(X, Y):
n, m = len(X)+1, len(Y)+1
dp = [["" for _ in range(m)] for _ in range(n)]
for i in range(1, n):
for j in range(1, m):
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-1][j], dp[i][j-1], key=len)
return dp[-1][-1]
result = ""
i, j = 0, 0
for s in lcs(str1, str2):
while str1[i] != s:
result += str1[i]
i += 1
while str2[j] != s:
result += str2[j]
j += 1
result += s
i, j = i+1, j+1
return result + str1[i:] + str2[j:]
#answer
str1, str2 = "abac", "cab"
print(Solution.shortestCommonSupersequence(str1, str2))
```