No.583 两个字符串的删除操作

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

提示：

给定单词的长度不超过500。
给定单词中的字符只含有小写字母。

思路分析

两个字符串求这种类似编辑距离的题基本上用二维动态规划都比较简单。这道题有两种思路（均为动态规划），一种正着想，一种倒着想。

正向思维

dp[i][j]表示答案，也就是word1中前i个字符和word2中前j个字符所组成的字符串的删除操作的最短步数。
那么边界条件首先是dp[i][0]=i(i <= word1.length)与dp[0][i]=i(i <= word2.length)。因为一个空字符串与一个长度为i的字符串，总是要把长度为i的字符串删空才能相等，所以边界条件就此确定。动态规划的转移方程为两个

dp[i + 1][j + 1] = dp[i][j] (a[i] == b[j])
dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1]) + 1 (a[i] != b[i])

第一行，相等的时候，因为当出现两个相等字符的时候，删除的距离一定不增加。第二行也很好理解，如果没法做到相同的字符，那么就只能在删掉一位的基础上再进行比较，那么会在取最小值之后再加上1。

逆向思维

既然是删除字符串中的某些字符，那么留下来的公共部分我们怎么称呼呢？仔细思考，便发现，这不就是最长公共子序列吗！
那么我们就可以先求出两个字符串最长公共子序列的长度，然后再用两个字符串的长度减去最长公共子序列两倍的长度，即可获得每边字符串需要减少的字符数量之和。边界条件dp[i][0]=0与dp[0][i]=0
动态规划的转移方程

dp[i + 1][j + 1] = dp[i][j] + 1 (a[i] == b[j])
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]) (a[i] != b[i])

也比较好理解。

C++代码（正向）

#define REP(i, j) for (int i = 0; i < j; ++i)
class Solution {
public:
    int minDistance(string a, string b) {
        int m = a.size(), n = b.size();
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof dp);
        REP(i, m) REP(j, n)
            if (a[i] == b[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
            else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
        return m + n - 2 * dp[m][n];
    }
};

C++代码（逆向）

#define REP(i, j) for (int i = 0; i < j; ++i)
class Solution {
public:
    int minDistance(string a, string b) {
        /*这破烂玩意不用dp做我把力扣炸了*/
        int m = a.size(), n = b.size();
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof dp);
        REP(i, m) REP(j, n)
            if (a[i] == b[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
            else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
        return m + n - 2 * dp[m][n];
    }
};

LeetCode Solution - 力扣题解