Shortest Common Supersequence in Python

# Shortest Common Supersequence in Python

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