本节内容

1. 两个字符串的删除操作
1. 编辑距离
编辑距离总结

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

建议：

题目链接： https://leetcode.cn/problems/delete-operation-for-two-strings/
文章讲解： 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
视频讲解：

题目分析

方案一

从 46、第九章动态规划part13 到现在我一直没看过官方的题解，导致我一直再用时间复杂度较高的方法去操作，本题也是。

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

结果

解答成功:
执行耗时:13 ms,击败了6.00% 的Java用户
内存消耗:41.1 MB,击败了99.26% 的Java用户

分析

时间复杂度：
O( n ^ 2 * m )

空间复杂度：
O( n )

代码随想录

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

动态规划一

本题和 115.不同的子序列 相比，其实就是两个字符串都可以删除了，情况虽说复杂一些，但整体思路是不变的。

这次是两个字符串可以相互删了，这种题目也知道用动态规划的思路来解，动规五部曲，分析如下：

确定dp数组（dp table）以及下标的含义

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

这里dp数组的定义有点点绕，大家要撸清思路。

确定递推公式

当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});

因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，所以递推公式可简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

这里可能不少录友有点迷糊，从字面上理解就是当同时删word1[i - 1]和word2[j - 1]，dp[i][j-1] 本来就不考虑 word2[j - 1]了，那么我在删 word1[i - 1]，是不是就达到两个元素都删除的效果，即 dp[i][j-1] + 1。

dp数组如何初始化

从递推公式中，可以看出来，dp[i][0] 和 dp[0][j]是一定要初始化的。

dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。

dp[0][j]的话同理，所以代码如下：

1
2
3

vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

确定遍历顺序

从递推公式 dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j], dp[i][j - 1]) + 1); 和dp[i][j] = dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。

所以遍历的时候一定是从上到下，从左到右，这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

举例推导dp数组

以word1:”sea”，word2:”eat”为例，推导dp数组状态图如下：

以上分析完毕，代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
        for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                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);
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

时间复杂度: O(n * m)
空间复杂度: O(n * m)

动态规划二

本题和 1143.最长公共子序列 基本相同，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
        for (int i=1; i<=word1.size(); i++){
            for (int j=1; j<=word2.size(); 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 word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;
    }
};

时间复杂度: O(n * m)
空间复杂度: O(n * m)

代码实现

// dp数组中存储word1和word2最长相同子序列的长度
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;
    }
}

// dp数组中存储需要删除的字符个数
class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;
        for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;
        
        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,
                                        Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        
        return dp[word1.length()][word2.length()];
    }
}

//DP - longest common subsequence (用最長公共子序列反推)
class Solution {
    public int minDistance(String word1, String word2) {
        char[] char1 = word1.toCharArray();
        char[] char2 = word2.toCharArray();

        int len1 = char1.length;
        int len2 = char2.length;

        int dp[][] = new int [len1 + 1][len2 + 1];

        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(char1[i - 1] == char2[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 - (2 * dp[len1][len2]);//和leetcode 1143只差在這一行。
    }
}

72. 编辑距离※

建议：

题目链接： https://leetcode.cn/problems/edit-distance/
文章讲解： https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html
视频讲解：

题目分析

方案一

我愿称我编写代码的方法为面向测试的代码编写，一步步打印dp数组调试出来的！！

class Solution {  
    public int minDistance(String word1, String word2) {  
        int[][] dp = new int[word2.length() + 1][word1.length() + 1];  
        for (int i = 1; i <= word1.length(); i++) {  
            dp[0][i] = i;  
        }  
        for (int i = 1; i <= word2.length(); i++) {  
            dp[i][0] = i;  
        }  
  
        for (int i = 1; i <= word2.length(); i++) {  
            for (int j = 1; j <= word1.length(); j++) {  
                if (word2.charAt(i - 1) == word1.charAt(j - 1)) {  
                    dp[i][j] = dp[i - 1][j - 1];  
                } else {  
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;  
                }  
            }  
  
//            for (int j = 1; j <= word1.length(); j++) {  
//                System.out.printf("    " + dp[i][j]);  
//            }  
//            System.out.println();  
        }  
        return dp[word2.length()][word1.length()];  
    }  
}

结果

解答成功:
执行耗时:5 ms,击败了45.25% 的Java用户
内存消耗:42.4 MB,击败了77.69% 的Java用户

分析

时间复杂度：
O( n * m )

空间复杂度：
O( n * m )

代码随想录

https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html

思路

编辑距离终于来了，这道题目如果大家没有了解动态规划的话，会感觉超级复杂。

编辑距离是用动规来解决的经典题目，这道题目看上去好像很复杂，但用动规可以很巧妙的算出最少编辑距离。

接下来我依然使用动规五部曲，对本题做一个详细的分析：

1. 确定dp数组（dp table）以及下标的含义

**dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]**。

有同学问了，为啥要表示下标i-1为结尾的字符串呢，为啥不表示下标i为结尾的字符串呢？

为什么这么定义我在 718. 最长重复子数组 中做了详细的讲解。

其实用i来表示也可以！用i-1就是为了方便后面dp数组初始化的。

2. 确定递推公式

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

if (word1[i - 1] == word2[j - 1])
    不操作
if (word1[i - 1] != word2[j - 1])
    增
    删
    换

也就是如上4种情况。

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删除一个元素，那么就是以下标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"，最终的操作数是一样！ dp数组如下图所示意的：

           a                         a     d
  +-----+-----+             +-----+-----+-----+
  |  0  |  1  |             |  0  |  1  |  2  |
  +-----+-----+   ===>      +-----+-----+-----+
a |  1  |  0  |           a |  1  |  0  |  1  |
  +-----+-----+             +-----+-----+-----+
d |  2  |  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;

递归公式代码如下：

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

3. dp数组如何初始化

再回顾一下dp[i][j]的定义：

**dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]**。

那么dp[i][0] 和 dp[0][j] 表示什么呢？

dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。

那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;

同理dp[0][j] = j;

所以C++代码如下：

1 2	`for (int i = 0; i <= word1.size(); i++) dp[i][0] = i; for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;`

4. 确定遍历顺序

从如下四个递推公式：

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

可以看出dp[i][j]是依赖左方，上方和左上方元素的，如图：

所以在dp矩阵中一定是从左到右从上到下去遍历。

代码如下：

for (int i = 1; i <= word1.size(); i++) {
    for (int j = 1; j <= word2.size(); j++) {
        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;
        }
    }
}

5. 举例推导dp数组

以示例1为例，输入：word1 = "horse", word2 = "ros"为例，dp矩阵状态图如下：

以上动规五部分析完毕，C++代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
        for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                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;
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

时间复杂度: O(n * m)
空间复杂度: O(n * m)

代码实现

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];
}

编辑距离总结※

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

判断子序列

https://www.yuanql.top/2023/08/19/02_1_%E4%BB%A3%E7%A0%81%E9%9A%8F%E6%83%B3%E5%BD%95%E7%AE%97%E6%B3%95%E8%AE%AD%E7%BB%83%E8%90%A518%E6%9C%9F/48%E3%80%81%E7%AC%AC%E4%B9%9D%E7%AB%A0%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92part15/#392-%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97%E2%80%BB

不同的子序列

https://www.yuanql.top/2023/08/19/02_1_%E4%BB%A3%E7%A0%81%E9%9A%8F%E6%83%B3%E5%BD%95%E7%AE%97%E6%B3%95%E8%AE%AD%E7%BB%83%E8%90%A518%E6%9C%9F/48%E3%80%81%E7%AC%AC%E4%B9%9D%E7%AB%A0%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92part15/#115-%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97%E2%80%BB

两个字符串的删除操作

https://www.yuanql.top/2023/08/20/02_1_%E4%BB%A3%E7%A0%81%E9%9A%8F%E6%83%B3%E5%BD%95%E7%AE%97%E6%B3%95%E8%AE%AD%E7%BB%83%E8%90%A518%E6%9C%9F/49%E3%80%81%E7%AC%AC%E4%B9%9D%E7%AB%A0%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92part16/#583-%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%E2%80%BB

编辑距离

02_1_代码随想录算法训练营18期

#LeetCode #算法训练营

49、第九章动态规划part16

http://yuanql.top/2023/08/20/02_1_代码随想录算法训练营18期/49、第九章动态规划part16/

作者

Qingli Yuan

发布于

2023年8月20日

许可协议

2023年8月20日每日一题--2236. 判断根结点是否等于子结点之和上一篇

2023年8月19日每日一题--2235. 两整数相加下一篇

49、第九章 动态规划part16

本节内容

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

题目分析

方案一

结果

分析

代码随想录

动态规划一

动态规划二

代码实现

72. 编辑距离※

题目分析

方案一

结果

分析

代码随想录

思路

1. 确定dp数组（dp table）以及下标的含义

2. 确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

5. 举例推导dp数组

代码实现

编辑距离总结※

判断子序列

不同的子序列

两个字符串的删除操作

编辑距离

49、第九章动态规划part16