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:
- The length of given words won’t exceed 500.
- 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
类似题目：
Minimum ASCII Delete Sum for Two Strings
参考资料：
https://leetcode.com/problems/delete-operation-for-two-strings/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
