1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
# 1092. Shortest Common Supersequence
"""
given two strings 's1' and 's2', return the shortest string that has both
s1 and s2 as subsequences. if there are multiple valid strings, return
any of them. a string 's' is a supersequence if string 't' if deleting some
number of characters from 't' (possibly 0) results in string 's'.
"""
class Solution(object):
def lcs(self, s1, s2):
n, m = len(s1), len(s2)
dp = [["" for i in range(m + 1)] for j in range(n + 1)]
for i in range(n):
for j in range(m):
if s1[i] == s2[j]:
dp[i + 1][j + 1] = dp[i][j] + s1[i]
else:
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1], key=len)
return dp[-1][-1]
def shortestCommonSupersequence(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: str
"""
ans, i, j = "", 0, 0
for c in self.lcs(s1, s2):
while s1[i] != c:
ans += s1[i]
i += 1
while s2[j] != c:
ans += s2[j]
j += 1
ans += c
i, j = i + 1, j + 1
return ans + s1[i:] + s2[j:]
if __name__ == "__main__":
obj = Solution()
print(obj.shortestCommonSupersequence(s1="abac", s2="cab"))
print(obj.shortestCommonSupersequence(s1="aaaaaaaa", s2="aaaaaaaa"))
|