目录

583. 两个字符串的删除操作

72. 编辑距离

编辑距离总结篇

583. 两个字符串的删除操作

dp数组的定义：

dp[i][j]，是以i-1为结尾的word1，j-1为结尾的word2,要让他们两个相等所需要的最少次数

递归公式

当word1[i-1] 和word2[j-1]相等的时候，也不用加一了，继承上面的次数

dp[i][j]=dp[i-1][j-1]

word1[i-1]和word2[j-1]不相等的时候

删掉word1[i-1]：

dp[i-1][j]+1

删掉word2[j-1]

dp[i][j-1]+1

同时删掉word1[i-1]和word2[j-1]，操作的最少次数为dp[i-1][j-1]+2

最后取最小值：

Min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2)

初始化

得初始化dp[i][0]和dp[0][j]

为删除多少个元素

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

代码随想录

72. 编辑距离

dp数组的定义

dp[i][j]代表i-1的word1和i-1的word2的最少操作数

递归公式：

当word1[i-1]==word2[i-1]:相同的时候

不需要操作dp[i][j]=dp[i-1][j-1]

不相同的时候：

删:

删除word[i-1]，所以是往上走一个

dp[i][j] = dp[i-1][j]

增：

word1增加一个元素，等于word2减少一个元素，他们的操作数是相同的。

word1 = ab word2 = a---删除

word1 = a word2 = ab---增加

一样的效果

替换：

dp[i][j] = dp[i-1][j-1]

后面都是要在这些后面加一个操作书
min( dp[i-1][j],dp[i-1][j-1]d,dp[i][j-1])+1

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
        for i in range(len(word1)+1):dp[i][0] = i
        for j in range(len(word2)+1):dp[0][j] = j
        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+1):
                #如果相等
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                #如果不相等
                else:
                #增删替换
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
        return dp[-1][-1]

代码随想录

编辑距离总结篇

做一个总结吧

代码随想录