---

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

思路

思路代码

在这里插入代码片

官方题解

代码

func minDistance(word1 string, word2 string) int {dp:=make([][]int,len(word1)+1)for i:=range dp{dp[i]=make([]int,len(word2)+1)}for i:=0;i<=len(word1);i++{dp[i][0]=i}for i:=0;i<=len(word2);i++{dp[0][i]=i}for i:=1;i<=len(word1);i++{for j:=1;j<=len(word2);j++{if word1[i-1]!=word2[j-1]{dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2)}else{dp[i][j]=dp[i-1][j-1]}}}return dp[len(word1)][len(word2)]
}func min(i,j int)int{if i<j{return i}else{return j}
}

困难

---

72. 编辑距离

官方题解

在整个动规的过程中，最为关键就是正确理解dp[i][j]的定义！

if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？

操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i - 1][j] + 1;

操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i][j - 1] + 1;

这里有同学发现了，怎么都是删除元素，添加元素去哪了。

word2添加一个元素，相当于word1删除一个元素，例如 word1 = “ad” ，word2 = “a”，word1删除元素’d’ 和 word2添加一个元素’d’，变成word1=“a”, word2=“ad”， 最终的操作数是一样！
操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增删加元素。

可以回顾一下，if (word1[i - 1] == word2[j - 1])的时候我们的操作 是 dp[i][j] = dp[i - 1][j - 1] 对吧。

那么只需要一次替换的操作，就可以让 word1[i - 1] 和 word2[j - 1] 相同。

所以 dp[i][j] = dp[i - 1][j - 1] + 1;

综上，当 if (word1[i - 1] != word2[j - 1]) 时取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

代码

func minDistance(word1 string, word2 string) int {m, n := len(word1), len(word2)dp := make([][]int, m+1)for i := range dp {dp[i] = make([]int, n+1)}for i := 0; i < m+1; i++ {dp[i][0] = i // word1[i] 变成 word2[0], 删掉 word1[i], 需要 i 部操作}for j := 0; j < n+1; j++ {dp[0][j] = j // word1[0] 变成 word2[j], 插入 word1[j]，需要 j 部操作}for i := 1; i < m+1; i++ {for j := 1; j < n+1; j++ {if word1[i-1] == word2[j-1] {dp[i][j] = dp[i-1][j-1]} else { // Min(插入，删除，替换)dp[i][j] = Min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1}}}return dp[m][n]
}
func Min(args ...int) int {min := args[0]for _, item := range args {if item < min {min = item}}return min
}

---

今日收获

编辑对应的增删改操作