代码随想录算法训练营打卡Day56 | LeetCode583 两个字符串的删除操作、LeetCode72 编辑距离

摘要

编辑距离问题中，插入一个字符和删除一个字符，对于使得两个字符串相等的作用是一样的，都是使得两个字符串更加接近，所以可以统一只使用“插入”或者只使用“删除”
可以进行”修改一个字符“这个操作时，不能再使用求最长公共子序列的长度的思路，因为dp数组只保存了长度信息，”修改一个字符“并不改变长度，dp数组没有这部分信息。

LeetCode583 两个字符串的删除操作

583. 两个字符串的删除操作 - 力扣（Leetcode）

初见题目的思路

初见题目的想法：求word1和word2的最长公共子序列的长度，因为从word1和word2中删除字符使word1和word2相同，相当于分别从word1和word2中删除字符，使得word1和word2都等于原来的word1和word2的最长公共子序列。
在代码随想录算法训练营打卡Day53中已经分析了如何用动态规划的思路求最长公共子序列，只需要利用一下dp数组就可以求出答案。
- 根据dp数组的定义，dp[word1.size()][word2.size()]就是最长公共子序列的长度
- word1要变成最长公共子序列需要删除的元素个数就是word1.size() - dp[word1.size()][word2.size()]。
- word2同理，变成最长公共子序列的删除步数为dp[word1.size()][word2.size()]

题解代码如下

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]);
            }
        }
        int steps1 = word1.size() - dp[word1.size()][word2.size()];
        int steps2 = word2.size() - dp[word1.size()][word2.size()];
        return steps1 + steps2;
    }
};

思路2

这个思路也是更接近“编辑距离”的思路，直接将dp数组定义为使word1和word2相同所需的最小操作步数。
dp数组及数组下标的含义：dp[i][j]的含义为，下标都是以0为开始，长度为i的字符串word1，和长度为j字符串word2，word1和word2要相等所需的删除字符的最少步数。
- word1结尾的字符下标为i-1，word2结尾的字符的下标为j-1
确定递推公式，dp[i][j]的值有如下可能
- 当word1[i-1] == word2[j-1]时，说明不需要删除这两个字符，不增加步数，步数为使i-1和j-1之前的字符串相等所需的步数， $dp[i][j]=dp[i-1][j-1]$
- 当word1[i-1] != word2[j-1]时
  1. 删除word1[i-1]，使得word1和word2能够相等，删除一个字符，步数在之前的字符串相等所需的步数的基础上+1， $dp[i][j] = dp[i-1][j]+1$
  2. 删除word2[j-1]，使得word1和word2能够相等，同理， $dp[i][j]=dp[i][j-1]+1$
  3. 删除word1[i-1]和word2[j-1]，使得word1和word2能够相等，这个情况已经被以上两个情况覆盖了，可写可不写。 $dp[i][j]=dp[i-1][j-1]+2$
  - 根据dp数组的定义，取可能值的最小值 $dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1)$
  - 再解释一下情况 3 为什么可以不写在递推公式中
    1. 从数学角度考虑 $dp[i-1][j] + 1 = dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2$
    2. 从dp数组的定义，选择同时删word1[i-1]和word2[j-1]，dp[i][j-1] 本来就不考虑 word2[j-1]了，那么再在dp[i][j-1] 的基础上删word1[i-1]，就达到两个元素都删除的效果了，即dp[i][j-1]+1。
初始化dp数组，根据dp数组的定义
- dp[i][0]的含义为，word1长度为i，word2长度为0，即word2为空字符串，已经不能再从word2中删除任何字符，所以只能是word1删除i个字符，让word1也变成空字符串。
- dp[0][j]同理。
- dp[0][0]，两个空字符串，不需要删除任何字符，两个空字符串本身就是相等的。
遍历顺序，i和j都是从小到大遍历

题解代码如下

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

        return dp[word1.size()][word2.size()];
    }
};

LeetCode72 编辑距离

72. 编辑距离 - 力扣（Leetcode）

这道题目首先要明确“插入一个字符”和“删除一个字符”这两个操作的本质是一样的，都是改变字符的个数来让word1和word2更“接近”。举一个简单的例子，word1="ab"; word2="a"。
- 插入一个字符，在word2后插入一个字符'b'。word2="ab"，插入一个字符可以使得word1和word2相等。
- 删除一个字符，在word1中将字符'b'删除。word1="a"，删除一个字符也可以使得word1和word2相等。
所以，其实可以只在“插入”和“删除”中选择其中一种操作，再加上“修改”这一种操作，就能使得word1和word2相等。
- “插入一个字符”和“修改一个字符”
- “删除一个字符”和“修改一个字符”
本次为了和之前的题目思路相近，所以统一选择用“删除一个字符”和“修改一个字符”来操作字符串。
dp数组及数组下标的含义：dp[i][j]表示，下标都是从0开始，长度为i的word1的子字符串和长度为j的word2的子字符串，让这两个字符串相等所需操作的最少步数。
递推公式，dp[i][j]的值有如下可能
- 当word1[i-1] == word2[j-1]时，说明不需要删除这两个字符，不增加步数，步数为使i-1和j-1之前的字符串相等所需的步数， $dp[i][j]=dp[i-1][j-1]$
- 当word1[i-1] != word2[j-1]时
  1. 如果选择修改一个字符，将word1[i-1]修改成word2[j-1]，或者将word2[j-1]修改成word1[i-1]，这就变成了word[i-1] == word2[j-1]的情况，不过因为修改了一个字符，所以步数+1。 $dp[i][j]=dp[i-1][j-1]+1$
  2. 如果不选择修改字符，那只有删除一个字符或者增加一个字符可选。根据前面简单的分析，删除一个字符和增加一个字符最终达到的效果都是让word1和word2更加接近。所以可以只用“删除”或者“增加”中的一个操作来理解dp数组。
    - 删除word1[i-1]，dp[i-1][j]本就是不考虑word1[i-1]的，但删除一个字符步数+1，所以 $dp[i][j]=dp[i-1][j]+1$ 。删除word1[i-1]，其实也可以是在已经比对完成的word2的子字符串后插入一个word[i-1]
    - 删除word[j-1]，dp[i][j-1]本就是不考虑word1[j-1]的，但删除一个字符步数+1，所以 $dp[i][j]=dp[i][j-1]+1$ 。
  - dp的值为最少步数，当然是取这些可能值的最小值，这些值都是由之前的状态再加一步，即+1得到的，所以可以把+1提出来 $dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j]+dp[i][j-1]))+1$
初始化dp数组，和上一题的思路其实是一样
- dp[i][0]的含义为，word1长度为i，word2长度为0，即word2为空字符串，已经不能再从word2中删除任何字符，所以只能是word1删除i个字符，让word1也变成空字符串。
- dp[0][j]同理。
- dp[0][0]，两个空字符串，不需要删除任何字符，两个空字符串本身就是相等的。
遍历顺序，i和j都是从小到大遍历
和上一题相比，其实就是递推公式中新增了dp[i][j]=dp[i-1][j-1]的可能来对应“修改一个字符”这个操作。

题解代码如下

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

        return dp[word1.size()][word2.size()];
    }
};