583. Delete Operation for Two Strings

Loading...LeetCode

求 Longest Common String，跟 common 有关的很多都是DP题，这题虽然是二维DP，状态转换方程还挺简单的。

bottom-up和top-down都能写，但top-down的结构在 Python 里实现起来有点tricky，而且也慢。bottom-up可以直接拿数组记录，简单一些。

Top-down

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = collections.defaultdict(lambda :collections.defaultdict(int))
        return len(word1) + len(word2) - 2 * self.LCS(word1, word2, m, n, dp)
        
    # longest common string
    def LCS(self, a, b, m, n, dp):
        if not m or not n:
            return 0
        if dp[m][n]:
            return dp[m][n]
        if a[m-1] == b[n-1]:
            dp[m][n] = 1 + self.LCS(a, b, m-1, n-1, dp)
        else:
            dp[m][n] = max([self.LCS(a, b, m-1, n, dp), self.LCS(a, b, m, n-1, dp)])
        return dp[m][n]

Bottom-up

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        if not m and not n: return 0
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    
        return m+n-2*dp[m][n]