583. Delete Operation for Two Strings

 

Given two words  word1  and  word2 , find the minimum number of steps required to make  word1  and  word2  the same, where in each step you can delete one character in either string.

Example 1:

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

 

Note:

  1. The length of given words won’t exceed 500.
  2. Characters in given words can only be lower-case letters.

 

这道题给了我们两个单词,问最少需要多少步可以让两个单词相等,每一步可以在任意一个单词中删掉一个字符。那么来分析怎么能让步数最少呢,是不是知道两个单词最长的相同子序列的长度,并乘以2,被两个单词的长度之和减,就是最少步数了。其实这道题就转换成求 Longest Common Subsequence 最长相同子序列的问题,令博主意外的是,LeetCode 中竟然没有这道题,这与包含万物的 LeetCode 的作风不符啊(现在已经补上了 Longest Common Subsequence)。不过没事,有这道题也行啊,对于这种玩字符串,并且是求极值的问题,十有八九都是用dp来解的,曾经有网友问博主,如何确定什么时候用 greedy,什么时候用 dp?其实博主也不不太清楚,感觉 dp 要更 tricky 一些,而且出现的概率大,所以博主一般会先考虑 dp,如果实在想不出状态转移方程,那么就想想 greedy 能做不。如果有大神知道更好的区分方法,请一定留言告知博主啊,多谢!那么决定了用 dp 来做,就定义一个二维的 dp 数组,其中 dp[i][j] 表示 word1 的前i个字符和 word2 的前j个字符组成的两个单词的最长公共子序列的长度。下面来看状态转移方程 dp[i][j] 怎么求,首先来考虑 dp[i][j] 和 dp[i-1][j-1] 之间的关系,可以发现,如果当前的两个字符相等,那么 dp[i][j] = dp[i-1][j-1] + 1,这不难理解吧,因为最长相同子序列又多了一个相同的字符,所以长度加1。由于 dp 数组的大小定义的是 (n1+1) x (n2+1),所以比较的是 word1[i-1] 和 word2[j-1]。如果这两个字符不相等呢,难道直接将 dp[i-1][j-1] 赋值给 dp[i][j] 吗,当然不是,这里还要错位相比嘛,比如就拿题目中的例子来说,”sea” 和 “eat”,当比较第一个字符,发现 ‘s’ 和 ‘e’ 不相等,下一步就要错位比较啊,比较 sea 中第一个 ‘s’ 和 eat 中的 ‘a’,sea 中的 ‘e’ 跟 eat 中的第一个 ‘e’ 相比,这样 dp[i][j] 就要取 dp[i-1][j] 跟 dp[i][j-1] 中的较大值了,最后求出了最大共同子序列的长度,就能直接算出最小步数了,参见代码如下:

 

解法一:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++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]);
                }
            }
        }
        return n1 + n2 - 2 * dp[n1][n2];
    }
};

 

下面这种方法也是用的 dp,但是和上面的 dp 思路不太一样,这种算法是跟之前那道 Edit Distance 相同的思路。那道题问一个单词通过多少步修改可以得到另一个单词,其实 word2 删除一个字符,和跟在 word1 对应的地方加上那个要删除的字符,达到的效果是一样的,并不影响最终的步骤数,所以这道题完全可以按照那道题的解法来做,一点都不需要变动,定义一个二维的 dp 数组,其中 dp[i][j] 表示 word1 的前i个字符和 word2 的前j个字符组成的两个单词,能使其变相同的最小的步数,讲解可以参看那篇帖子,参见代码入下:

 

解法二:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
        for (int i = 0; i <= n1; ++i) dp[i][0] = i;
        for (int j = 0; j <= n2; ++j) dp[0][j] = j;
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n1][n2];
    }
};

 

下面这种方法是解法二的递归写法,用的优化的 dfs 的方法,用 memo 数组来保存中间计算结果,以避免大量的重复计算,参见代码如下:

 

解法三:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        vector<vector<int>> memo(n1 + 1, vector<int>(n2 + 1, 0));
        return helper(word1, word2, 0, 0, memo);
    }
    int helper(string word1, string word2, int p1, int p2, vector<vector<int>>& memo) {
        if (memo[p1][p2] != 0) return memo[p1][p2];
        int n1 = word1.size(), n2 = word2.size();
        if (p1 == n1 || p2 == n2) return n1 - p1 + n2 - p2;
        if (word1[p1] == word2[p2]) {
            memo[p1][p2] = helper(word1, word2, p1 + 1, p2 + 1, memo);
        } else {
            memo[p1][p2] = 1 + min(helper(word1, word2, p1 + 1, p2, memo), helper(word1, word2, p1, p2 + 1, memo));
        }
        return memo[p1][p2];
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/583

 

类似题目:

Edit Distance

Minimum ASCII Delete Sum for Two Strings

Longest Common Subsequence

 

参考资料:

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

https://leetcode.com/problems/delete-operation-for-two-strings/discuss/103273/dynamic-programming-and-memoization-solution

https://leetcode.com/problems/delete-operation-for-two-strings/discuss/103214/Java-DP-Solution-(Longest-Common-Subsequence)

https://leetcode.com/problems/delete-operation-for-two-strings/discuss/103258/two-pointers-recursive-java-solution-with-memoization

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation