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] + 118 self.b[i+1][j+1] = 119 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] = 223 else:24 self.dp[i+1][j+1] = self.dp[i][j+1]25 self.b[i+1][j+1] = 326 27 def printLCS(self,str1,str2,i,j):28 if i == 0 or j == 0:29 return30 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.LCStr34 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 result52 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 + str258 else:59 return self.generateStr(str1,str2)
写得有点复杂了，好在AC了。对我而言，hard难度的题目，能做出来算是不错了，效率上就不能做太高要求了。
本题的主要思想：先求两个字符串的最长公共子序列（LCS），然后再把不是最长公共子序列中的字符按任意顺序拼接在一起。
这里拼接策略是先补充str1中的字符，再补充str2中的字符。