代码随想录算法训练营第五十五天| ● 583. 两个字符串的删除操作 ● 72. 编辑距离 ● 编辑距离总结篇

两个字符串的删除操作 

题目链接：583. 两个字符串的删除操作 - 力扣（LeetCode）

思路：第一次尝试用画图法，然后肉眼观察dp递归规律……但是dp[i][j]的含义还是参考昨天的思路，表示到此处需要删除多少个字符。

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

编辑距离 

题目链接：72. 编辑距离 - 力扣（LeetCode）

思路：又一次肉眼观察法，但是还是借助部分没有通过的样例来完善自己的dp公式，实在不行输出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() + 1; i++)
            dp[i][0] = i;
        for (int i = 0; i < word2.size() + 1; i++)
            dp[0][i] = i;

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

不过可以学习一下min的写法，不用连个min，

 dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

编辑距离总结篇   

代码随想录 (programmercarl.com)

这里放一下官网上写的比较好的一个总结：

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

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