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:]
#answer
str1, str2 = "abac", "cab"
print(Solution.shortestCommonSupersequence(str1, str2))