【动态规划】代码随想录算法训练营第五十五天 |583. 两个字符串的删除操作， 72. 编辑距离，编辑距离总结篇（待补充）

绝地灬酷狼 2024-04-23 04:40 63阅读 0赞

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

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

*  输入: "sea", "eat"
 *  输出: 2
 *  解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

4、视频链接：

[动态规划之子序列，还是为了编辑距离做铺垫 | LeetCode：583.两个字符串的删除操作\_哔哩哔哩\_bilibili][_ LeetCode_583._bilibili]

class Solution {
        public int minDistance(String word1, String word2) {
            int len1 = word1.length();
            int len2 = word2.length();
            int[][] dp = new int[len1 + 1][len2 + 1];
    
            for (int i = 1; i <= len1; i++) {
                for (int j = 1; j <= len2; j++) {
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            return len1 + len2 - dp[len1][len2] * 2;
        }
    }

## 72. 编辑距离 ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

*  插入一个字符
 *  删除一个字符
 *  替换一个字符
 *  示例 1：
 *  输入：word1 = "horse", word2 = "ros"
 *  输出：3
 *  解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
 *  示例 2：
 *  输入：word1 = "intention", word2 = "execution"
 *  输出：5
 *  解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')

提示：

*  0 <= word1.length, word2.length <= 500
 *  word1 和 word2 由小写英文字母组成

4、视频链接：

[动态规划终极绝杀！ LeetCode：72.编辑距离\_哔哩哔哩\_bilibili][LeetCode_72._bilibili]

class Solution {
        public int minDistance(String word1, String word2) {
            int m = word1.length();
            int n = word2.length();
            int[][] dp = new int[m + 1][n + 1];
            // 初始化
            for (int i = 1; i <= m; i++) {
                dp[i][0] = i;
            }
            for (int j = 1; j <= n; j++) {
                dp[0][j] = j;
            }
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    // 因为dp数组有效位从1开始
                    // 所以当前遍历到的字符串的位置为i-1 | j-1
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
                    }
                }
            }
            return dp[m][n];
        }
    }

## 编辑距离总结篇 ##

本周我们讲了动态规划之终极绝杀：编辑距离，为什么叫做终极绝杀呢？

细心的录友应该知道，我们在前三篇动态规划的文章就一直为 编辑距离 这道题目做铺垫。

### [\#][Link 3]判断子序列 ###

[动态规划：392.判断子序列(opens new window)][392._opens new window]给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

这道题目 其实是可以用双指针或者贪心的的，但是我在开篇的时候就说了这是编辑距离的入门题目，因为从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况。

*  if (s\[i - 1\] == t\[j - 1\])

*   *  t中找到了一个字符在s中也出现了

*  if (s\[i - 1\] != t\[j - 1\])

*   *  相当于t要删除元素，继续匹配

状态转移方程：

if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
    else dp[i][j] = dp[i][j - 1];

### [\#][Link 4]不同的子序列 ###

[动态规划：115.不同的子序列(opens new window)][115._opens new window]给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

本题虽然也只有删除操作，不用考虑替换增加之类的，但相对于[动态规划：392.判断子序列(opens new window)][392._opens new window]就有难度了，这道题目双指针法可就做不了。

当s\[i - 1\] 与 t\[j - 1\]相等时，dp\[i\]\[j\]可以有两部分组成。

一部分是用s\[i - 1\]来匹配，那么个数为dp\[i - 1\]\[j - 1\]。

一部分是不用s\[i - 1\]来匹配，个数为dp\[i - 1\]\[j\]。

这里可能有同学不明白了，为什么还要考虑 不用s\[i - 1\]来匹配，都相同了指定要匹配啊。

例如： s：bagg 和 t：bag ，s\[3\] 和 t\[2\]是相同的，但是字符串s也可以不用s\[3\]来匹配，即用s\[0\]s\[1\]s\[2\]组成的bag。

当然也可以用s\[3\]来匹配，即：s\[0\]s\[1\]s\[3\]组成的bag。

所以当s\[i - 1\] 与 t\[j - 1\]相等时，dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + dp\[i - 1\]\[j\];

当s\[i - 1\] 与 t\[j - 1\]不相等时，dp\[i\]\[j\]只有一部分组成，不用s\[i - 1\]来匹配，即：dp\[i - 1\]\[j\]

所以递推公式为：dp\[i\]\[j\] = dp\[i - 1\]\[j\];

状态转移方程：

if (s[i - 1] == t[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    } else {
        dp[i][j] = dp[i - 1][j];
    }

### [\#][Link 5]两个字符串的删除操作 ###

[动态规划：583.两个字符串的删除操作(opens new window)][583._opens new window]给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最少步数，每步可以删除任意一个字符串中的一个字符。

本题和[动态规划：115.不同的子序列(opens new window)][115._opens new window]相比，其实就是两个字符串可以都可以删除了，情况虽说复杂一些，但整体思路是不变的。

*  当word1\[i - 1\] 与 word2\[j - 1\]相同的时候
 *  当word1\[i - 1\] 与 word2\[j - 1\]不相同的时候

当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

那最后当然是取最小值，所以当word1\[i - 1\] 与 word2\[j - 1\]不相同的时候，递推公式：dp\[i\]\[j\] = min(\{dp\[i - 1\]\[j - 1\] + 2, dp\[i - 1\]\[j\] + 1, dp\[i\]\[j - 1\] + 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] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
    }

### [\#][Link 6]编辑距离 ###

[动态规划：72.编辑距离(opens new window)][72._opens new window]给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

编辑距离终于来了，**有了前面三道题目的铺垫，应该有思路了**，本题是两个字符串可以增删改，比 [动态规划：判断子序列(opens new window)][392._opens new window]，[动态规划：不同的子序列(opens new window)][115._opens new window]，[动态规划：两个字符串的删除操作(opens new window)][583._opens new window]都要复杂的多。

在确定递推公式的时候，首先要考虑清楚编辑的几种操作，整理如下：

*  if (word1\[i - 1\] == word2\[j - 1\])

*   *  不操作

*  if (word1\[i - 1\] != word2\[j - 1\])

*   *  增
     *  删
     *  换

也就是如上四种情况。

if (word1\[i - 1\] == word2\[j - 1\]) 那么说明不用任何编辑，dp\[i\]\[j\] 就应该是 dp\[i - 1\]\[j - 1\]，即dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\];

此时可能有同学有点不明白，为啥要即dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\]呢？

那么就在回顾上面讲过的dp\[i\]\[j\]的定义，word1\[i - 1\] 与 word2\[j - 1\]相等了，那么就不用编辑了，以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp\[i - 1\]\[j - 1\] 就是 dp\[i\]\[j\]了。

在下面的讲解中，如果哪里看不懂，就回想一下dp\[i\]\[j\]的定义，就明白了。

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

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

操作一：word1增加一个元素，使其word1\[i - 1\]与word2\[j - 1\]相同，那么就是以下标i-2为结尾的word1 与 i-1为结尾的word2的最近编辑距离 加上一个增加元素的操作。

即 dp\[i\]\[j\] = dp\[i - 1\]\[j\] + 1;

操作二：word2添加一个元素，使其word1\[i - 1\]与word2\[j - 1\]相同，那么就是以下标i-1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个增加元素的操作。

即 dp\[i\]\[j\] = dp\[i\]\[j - 1\] + 1;

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

**word2添加一个元素，相当于word1删除一个元素**，例如 word1 = "ad" ，word2 = "a"，word2添加一个元素d，也就是相当于word1删除一个元素d，操作数是一样！

操作三：替换元素，word1替换word1\[i - 1\]，使其与word2\[j - 1\]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。

即 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;

递归公式代码如下：

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 - 1][j], dp[i][j - 1]}) + 1;
    }

### [\#][Link 7]总结 ###

心思的录友应该会发现我用了三道题做铺垫，才最后引出了[动态规划：72.编辑距离(opens new window)][72._opens new window]，Carl的良苦用心呀，你们体会到了嘛！

### [\#][Link 8]其他语言版本 ###

#### [\#][Link 9]Java： ####

class Solution {
        public int minDistance(String word1, String word2) {
            int m = word1.length();
            int n = word2.length();
            int[][] dp = new int[m+1][n+1];
            for(int i = 1; i <= m; i++){
                dp[i][0] = i;
            }
            for(int i = 1; i <= n; i++){
                dp[0][i] = i;
            }
            for(int i = 1; i <= m; i++){
                for(int j = 1; j <= n; j++){
                    int left = dp[i][j-1]+1;
                    int mid = dp[i-1][j-1];
                    int right = dp[i-1][j]+1;
                    if(word1.charAt(i-1) != word2.charAt(j-1)){
                        mid ++;
                    }
                    dp[i][j] = Math.min(left,Math.min(mid,right));
                }
            }
            return dp[m][n];
        }
    }

[. - _LeetCode]: https://leetcode.cn/problems/delete-operation-for-two-strings/
[Link 1]: https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_583._bilibili]: https://www.bilibili.com/video/BV1we4y157wB/
[. - _LeetCode 1]: https://leetcode.cn/problems/edit-distance/
[Link 2]: https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_72._bilibili]: https://www.bilibili.com/video/BV1qv4y1q78f/
[Link 3]: https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html#%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97
[392._opens new window]: https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html
[Link 4]: https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html#%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97
[115._opens new window]: https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html
[Link 5]: https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html#%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C
[583._opens new window]: https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html
[Link 6]: https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html#%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB
[72._opens new window]: https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html
[Link 7]: https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html#%E6%80%BB%E7%BB%93
[Link 8]: https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC
[Link 9]: https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html#java