Longest Common Substring (Shortest Common Superstring)

https://leetcode.com/problems/shortest-common-supersequence/

这两个问题是相同的其实

以下是Bottom-up DP的做法

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        def lcs(str1,str2):
            m = len(str1)
            n = len(str2)
            dp= [[""]*(1+n) for _ in range(m+1)]
            for i in range(1,m+1):
                for j in range(1,n+1):
                    if str1[i-1] == str2[j-1]:
                        dp[i][j] = dp[i-1][j-1] + str1[i-1]
                    else:
                        dp[i][j] = max(dp[i-1][j],dp[i][j-1],key=len)
            return dp[-1][-1]
        
        res =""
        i = 0
        j = 0
        #print(lcs(str1,str2))
        for c in lcs(str1,str2):
            while str1[i] != c:
                res+=str1[i]
                i+=1
            while str2[j] != c:
                res+= str2[j]
                j+=1
            res += c
            i+=1
            j+=1
        
        return res + str1[i:] + str2[j:]

当然用recursion也是可以做的，需要用一个cache来存之前recursion计算过的值这样可以把recursion的O(2^N)的降为O(MN)

m = len(text1)
        n = len(text2)
        self.dp=[n*[0] for _ in range(m)]
        def lcm(s1,s2,i,j):
            if i >= len(s1) or j >= len(s2):
                return 0
            if self.dp[i][j] != 0:
                return self.dp[i][j]
            if s1[i] == s2[j]:
                self.dp[i][j] = lcm(s1,s2,i+1,j+1)+1
                return self.dp[i][j]
            self.dp[i][j]=  max(lcm(s1,s2,i,j+1),lcm(s1,s2,i+1,j))
            return self.dp[i][j]
        return lcm(text1,text2,0,0)

这个recursion若用DP做法如下

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        dp=[(1+n)*[0] for _ in range(m+1)]
        res=0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        
                res = max(res,dp[i][j])
        return res