leetcode1092

 1 class Solution:
 2     def __init__(self):
 3         self.dp = []
 4         self.b = []
 5         self.LCStr = ''
 6         self.stridx1 = []
 7         self.stridx2 = []
 8 
 9     def LCS(self,str1,str2):
10         m = len(str1)
11         n = len(str2)
12         self.dp = [[0 for _ in range(n+1)]for _ in range(m+1)]
13         self.b = [[0 for _ in range(n+1)]for _ in range(m+1)]
14         for i in range(m):
15             for j in range(n):
16                 if str1[i] == str2[j]:
17                     self.dp[i+1][j+1] = self.dp[i][j] + 1
18                     self.b[i+1][j+1] = 1
19                 else:
20                     if self.dp[i+1][j] >= self.dp[i][j+1]:
21                         self.dp[i+1][j+1] = self.dp[i+1][j]
22                         self.b[i+1][j+1] = 2
23                     else:
24                         self.dp[i+1][j+1] = self.dp[i][j+1]
25                         self.b[i+1][j+1] = 3
26 
27     def printLCS(self,str1,str2,i,j):
28         if i == 0 or j == 0:
29             return
30         if self.b[i][j] == 1:
31             self.stridx1.insert(0,i-1)
32             self.stridx2.insert(0,j-1)
33             self.LCStr = str1[i-1] + self.LCStr
34             self.printLCS(str1,str2,i-1,j-1)
35         elif self.b[i][j] == 2:
36             self.printLCS(str1,str2,i,j-1)
37         else:
38             self.printLCS(str1,str2,i-1,j)
39 
40     def generateStr(self,str1,str2):
41         k = len(self.LCStr)
42         result = ''
43         result += str1[:self.stridx1[0]] + str2[:self.stridx2[0]] + self.LCStr[0]
44 
45         if k >= 2:
46             for i in range(1,k):
47                 result += str1[self.stridx1[i-1]+1:self.stridx1[i]] + str2[self.stridx2[i-1]+1:self.stridx2[i]]
48                 result += self.LCStr[i]
49 
50         result += str1[self.stridx1[k-1]+1:] + str2[self.stridx2[k-1]+1:]
51         return result
52 
53     def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
54         self.LCS(str1,str2)
55         self.printLCS(str1,str2,len(str1),len(str2))
56         if len(self.LCStr) == 0:
57             return str1 + str2
58         else:
59             return self.generateStr(str1,str2)

写得有点复杂了，好在AC了。对我而言，hard难度的题目，能做出来算是不错了，效率上就不能做太高要求了。

本题的主要思想：先求两个字符串的最长公共子序列（LCS），然后再把不是最长公共子序列中的字符按任意顺序拼接在一起。

这里拼接策略是先补充str1中的字符，再补充str2中的字符。