题目：583. 两个字符串的删除操作
思路：
还是最长公共子序列，假设最长公共子序列长度是l；那么需要删除的次数是len(s1) - l + len(s2) - l
代码：
func minDistance(word1 string, word2 string) int {
lens1 := len(word1)
lens2 := len(word2)
dp := make([][]int, lens1 + 1)
for i := 0; i <= lens1; i++ {
dp[i] = make([]int, lens2 + 1)
}
for i := 1; i <=lens1; i++ {
for j := 1; j <= lens2; j++ {
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 lens1 + lens2 - 2 * dp[lens1][lens2]
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
参考：
题目：72. 编辑距离
思路：
if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];
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; -
操作三：替换元素，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 {
lens1, lens2 := len(word1),len(word2)
dp := make([][]int, lens1 + 1)
for i := range dp {
dp[i] = make([]int, lens2+1)
}
for i:=0; i <= lens1; i++ {
dp[i][0] = i
}
for j:=0; j <= lens2; j++ {
dp[0][j] = j
}
for i := 1; i <=lens1; i++ {
for j :=1; j <= lens2; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
}else {
dp[i][j] = min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) + 1
}
}
}
return dp[lens1][lens2]
}
func min(a,b int)int{
if a < b {
return a
}
return b
}