代码随想录算法训练营第55天| Leetcode 583. 两个字符串的删除操作、Leetcode 72. 编辑距离

文章目录

• • Leetcode 583. 两个字符串的删除操作
  • Leetcode 72. 编辑距离

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

题目链接：Leetcode 583. 两个字符串的删除操作
题目描述： 给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步可以删除任意一个字符串中的一个字符。

思路： 本题其实可以利用Leetcode 1143.最长公共子序列这道题的思路，求出最长公共子序列之后，剩下的字符都要被删除。（最小步数 = 字符串字符总和 - 2 * 最长公共子序列）
代码如下：（方法一）

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> dp(n + 5, vector<int>(m + 5));
        //求最长公共子序列的模板
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ ){
                if(word1[i - 1] == word2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        //最小步数 = 字符串字符总和 - 2 * 最长公共子序列
        return n + m - 2 * dp[n][m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 时间复杂度: $O(n\times m)$
• 空间复杂度: $O(n\times m)$

当然，本题也可以按照正常删除的思路来解决：
代码如下：（方法二）

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> dp(n + 5, vector<int>(m + 5));
        //初始化
        for(int i = 0; i <= n; i ++ ) dp[i][0] = i;
        for(int j = 0; j <= m; j ++ ) dp[0][j] = j;

        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; 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] + 2, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }  
        return dp[n][m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 时间复杂度: $O(n\times m)$
• 空间复杂度: $O(n\times m)$

Leetcode 72. 编辑距离

题目链接： Leetcode 72. 编辑距离
题目描述： 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

思路： 本题属于动态规划的经典问题。
代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> dp(n + 5, vector<int>(m + 5));
        //初始化
        for(int i = 0; i <= n; i ++) dp[i][0] = i;
        for(int j = 0; j <= m; j ++) dp[0][j] = j;
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ ){
                if(word1[i - 1] == word2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];//不操作
                }else{//分别代表：word1字符串改，增，删一个字符
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        return dp[n][m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 时间复杂度: $O(n\times m)$
• 空间复杂度: $O(n\times m)$

---

总结： 有了前面题目的铺垫，这两道题很轻松

最后，如果文章有错误，请在评论区或私信指出，让我们共同进步！