Delete Operation for Two Strings

此题就是一道动态规划题，但是因为里面对字符串的修改限制在了删除一个操作上，实际上这道题可以通过两个不同的DP算法来实现了，我们可以从LCS的角度思考，这样我们需要进行的删除操作就变成了两个字符串的长度减去LCS长度的两倍

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        n, m = len(word1), len(word2)
        dp = [[0] * (m + 1) for _ in xrange(n + 1)]

        for i in xrange(1, n + 1):
            for j in xrange(1, m + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j - 1], dp[i - 1][j])
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

        return n + m - dp[n][m] * 2

而另外一个思路就是这种字符串操作常使用的edit distance思路了，利用edit distance里面的删除这个功能就可以构建这道题的DP矩阵

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        n, m = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in xrange(m + 1)]
        for i in xrange(m + 1):
            for j in xrange(n + 1):
                if not i:
                    dp[i][j] = j
                elif not j:
                    dp[i][j] = i
                elif word1[j - 1] == word2[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
        return dp[m][n]