【leetcode】583. 两个字符串的删除操作

距离上次更新本文已经过去了 213 天，文章部分内容可能已经过时，请注意甄别

leetcode 刷题笔记 - 583. 两个字符串的删除操作。

题目

https://leetcode.cn/problems/delete-operation-for-two-strings/

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

plaintext

示例 1：
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例  2:
输入：word1 = "leetcode", word2 = "etco"
输出：4

提示

plaintext

1 2	1 <= word1.length, word2.length <= 500 word1 和 word2 只包含小写英文字母

思路

本题要求将两个字符串变成相同的字符串，对于给出的所有用例，肯定是能变成相同的，最大的删除操作数就是将两个字符串的所有字符都删除（即两个字符串的长度之和），此时会得到两个空字符串，空字符串自然是相等的。至于其他情况，需要求的是最少操作次数，我们需要用动态规划的思路来解题。

这道题和之前写过的 115 题：不同的子序列非常相似，在 115 题中，是用 s 的子序列去匹配 t 整个字符串，t 字符串不能改变，只能在 s 中删除字母。但本题是求两个字符串怎么通过一些操作变成相同的字符串，每一步都可以从两个字符串其中一个字符串中删除一个字符，两个字符串都能被修改。

先来走动态规划的流程吧！第一步是确定 dp 数组的含义。

dp[i][j]：字符串 a 中下标 i-1 和字符串 b 中下标 i-1 及其之前的字符串需要至少几次操作能变成相同的字符串。
这里也可以理解为字符串 a 中前 i 个字符组成的字符串与字符串 b 中前 j 个字符组成的字符串需要至少几次操作能变成相同的字符串。

cpp

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

然后是确定递推公式

情况一：a[i-1] == b[j-1]，此时不需要删除字符，沿用 dp[i-1][j-1] 的结果就行了。
情况二：a[i-1] != b[j-1]，此时需要删除字符，有三种删除方式，取其中最小值即可：
- 删除 a 中的字符，结果为 dp[i-1][j]+1;
- 删除 b 中的字符，结果为 dp[i][j-1]+1;
- 把 a 和 b 中的这俩字符都删了，结果为 dp[i-1][j-1]+2;

dp 数组的遍历顺序，因为 dp[i][j] 很明显是依赖于 dp[i-1][j-1] 的，所以需要从左到右遍历。

再确定如何初始化 dp 数组，也分为三种情况：

i=0,j=0 的情况，两个都是空字符串，不需要做删除操作，初始化为 0；
i=0 或 j=0 的情况，一个是空字符串，另外一个字符串需要做的操作次数是字符串的长度次。

最终的初始化代码如下

cpp

// i和j都为0的时候不需要操作，初始化为0（通过构造函数初始化）
// 当i=0或者j=0的时候，需要的操作次数是当前的字符串长度，即需要将当前字符串全部删除才能和空字符串相同
for (int i = 1; i <= word1.size(); i++) {
    dp[i][0] = i;
}
for (int j = 1; j <= word2.size(); j++) {
    dp[0][j] = j;
}

代码

完整代码如下，思路明白了代码还是很好写的

cpp

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 如果有一个长度为0，那么需要做的操作是另外一个字符串的长度次
        if (word1.size() == 0 || word2.size() == 0) {
            return word1.size() == 0 ? word2.size() : word1.size();
        }
        // dp数组，代表a中i-1和b中j-1的字符串相同需要操作的最少次数（i和j可以认为是字符串长度）
        vector<vector<int>> dp(word1.size() + 1,
                               vector<int>(word2.size() + 1, 0));
        // i和j都为0的时候不需要操作，初始化为0（通过构造函数初始化）
        // 当i=0或者j=0的时候，需要的操作次数是当前的字符串长度，即需要将当前字符串全部删除才能和空字符串相同
        for (int i = 1; i <= word1.size(); i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= word2.size(); j++) {
            dp[0][j] = j;
        }
        // 开始递推
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                // 情况1，二者相同，不需要删除
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else // 情况2，不同
                {
                    // 把word1中的字符串删除，需要的操作次数是dp[i-1][j]+1
                    // 把word2中的字符串删除，需要的操作次数是dp[i][j-1]+1
                    // 把word1和2中的字符串都删除，需要的操作次数是dp[i-1][j-1]+2
                    // 取三种情况最小值作为最终结果。
                    dp[i][j] = min(dp[i - 1][j] + 1,
                                   min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2));
                }
            }
        }
        // dp数组右下角的值就是最终结果
        return dp[word1.size()][word2.size()];
    }
};