一、前言

参考文献：代码随想录

今天的主要内容还是编辑距离（字符串的删除）；今天的多了一些条件，不再只是一个匹配字符串和一个标准字符串了，而是两个字符串去匹配，找到两个相等的部分之后去返回修改的次数；

以及路径编辑问题；

二、两个字符串的删除操作

1、思路：

这里和上一次的不同子序列相同，只是返回值的类型不同罢了；

（1）dp数组的定义：

vector<vector<int>> dp(word1.size() + 1, vector<int> (word2.size() + 1, 0));

使用的还是长度+1的字符串数组，方便初始化；

（2）递推公式：

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); // 记得给删除的数量 + 1；
}

这里也是两种情况，但是在不相等的情况下出现了两种情况，一个是删除word1中的字符串另一个是删除word2中的字符串；

（3）初始化：

道理与上一次的相同，就是当一个字符串为空时，另一个需要删除几次才可以匹配上（也就是删除当前数组的长度）：

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

2、整体代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 1、定义dp数组
        vector<vector<int>> dp(word1.size() + 1, vector<int> (word2.size() + 1, 0));
        // 2、初始化
        for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
        for (int i = 0; i <= word2.size(); i++) dp[0][i] = i;
        // 3、顺序
        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); // 记得给删除的数量 + 1；
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

三、编辑距离

1、思路：

与上题差不多，但是这里我们分析他的递推公式：

本题目求的是最少编辑次数，那么可以增删改，那么就有三种情况需要处理：

但是发现，增和删属于同一类情况，只是参考物不一样；

那么就有如下代码：

              if (word1[i - 1] == word2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else
                {
                    // 不等于的情况下有三种操作：添加元素、删除元素、替换元素
                    /*
                        添加元素和删除元素：
                        可以看作是一类，我添加了一个元素，相当于旁边删除了一个元素（也就是参照物发什么变化）
                        替换元素：
                        就是让word1 and word2相等即可，也就是在dp[i - 1][j - 1]的基础上修改一个数组即可
                    */
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i -1][j], dp[i][j - 1])) + 1;
                }

解释在注释中 

2、整体代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 1、创建dp数组
        vector<vector<int>> dp(word1.size() + 1, vector<int> (word2.size() + 1, 0));
        // 2、初始化
        // 当word1或者word2变得越来越长时，就需要删除的元素来对应空字符串
        for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
        for (int i = 0; i <= word2.size(); i++) dp[0][i] = i;
        // 3、遍历顺序
        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
                {
                    // 不等于的情况下有三种操作：添加元素、删除元素、替换元素
                    /*
                        添加元素和删除元素：
                        可以看作是一类，我添加了一个元素，相当于旁边删除了一个元素（也就是参照物发什么变化）
                        替换元素：
                        就是让word1 and word2相等即可，也就是在dp[i - 1][j - 1]的基础上修改一个数组即可
                    */
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i -1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[word1.size()][word2.size()];
    } 
};

 Study time:1h.

Leave message:

What we have once enjoyed deeply we can never lose. All that we love deeply becomes a part us.

我们永远也不会失去那些曾尽情享受过的东西，因为我们深爱的一切都会成为我们自身的一部分。