Given two strings
str2, return the shortest string that has both
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.)
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.
1 <= str1.length, str2.length <= 1000 str1 and str2 consist of lowercase English letters.
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))