今天是我坚持写题解的第 52 天！

题目描述（Medium）

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

示例：

输入: "sea", "eat" 

输出: 2 

解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

提示：

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

链接：https://leetcode-cn.com/problems/delete-operation-for-two-strings

方法一、动态规划

今天这道题与 1143. 最长公共子序列 是一样的，我们只要求出了最长公共子序列的长度，拿两个字符串的长度之和减去2倍的最长公共子序列的长度就可以了。

好了，我们来看怎么求最长公共子序列呢？

我们可以使用动态规划来求解：

1. 状态定义：dp[i][j]
   表示 word1 的前 i 个字符与 word2 的前 j 个字符的最长公共子序列。
2. 状态转移：（1）如果 word1[i-1] == word2[j-1]，那么 dp[i][j]=dp[i-1][j-1]+1
   ，表示当前位置相等，可以从前一位转移过来，同时，加上当前的一个字符长度。（2）如果 word1[i-1] != word2[j-1]，那么 dp[i][j]=Math.max(dp[i][j-1], dp[i-1][j])
   ，表示不使用word2[j-1]，或者不使用word1[i-1]时的情况，而这两种情况之前已经计算过了，取其中的最大值转移过来。
3. 初始状态：dp[0][0] = 0
   ，表示两者前 0 个字符的最长公共子序列的长度，显然为 0。
4. 返回值：dp[m][n]
   ，其中，m 为 word1 的长度，n 为 word2 的长度。
5. 注意：我们这里 dp 定义的是 前 x 个字符，所以，与字符串的下标正好相差 1。

请看代码：

class Solution {
    public int minDistance(String word1, String word2) {
        // dp[i][j]表示w1的前i个字符与w2的前j个字符的最长公共子序列
        // 1. 如果w1[i-1]==w2[j-1]，dp[i][j]=dp[i-1][j-1]+1
        // 2. 如果w1[i-1]!=w2[j-1]，dp[i][j]=Math.max(dp[i][j-1], dp[i-1][j])
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return m + n - 2 * dp[m][n];
    }
}

• 时间复杂度：。
• 空间复杂度：。

运行结果如下：

方法二、动态规划 + 优化

方法一中，我们可以看到，dp 转移方程只与前一行或者前一列 有关，所以，我们可以把二维降到一维，只保留前一行或者前一列的数据即可，假设我们保留前一行，那么 dp 转移方程也只与前一列的旧值有关，所以，我们不需要声明两个一维数组，只需要稍加两个变量就可以达到效果。

请看代码：

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i <= m; i++) {
            int last = 0;
            for (int j = 1; j <= n; j++) {
                // 旧值，表示上一行的dp[j]
                int old = dp[j];
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // 这里使用的是之前的j，也就是j-1，即dp[j-1]的旧值
                    dp[j] = last + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                // last记录的是旧值，表示上一行的dp[j]
                last = old;
            }
        }
        return m + n - 2 * dp[n];
    }
}

• 时间复杂度：。
• 空间复杂度：，此处是记录一行的值，也可以记录一列的值，所以，可以根据 m 和 n 的大小去构造 dp 数组，最终可以优化到 的额外空间复杂度。

运行结果如下：

最后

如果对你有帮助，请点个赞吧，谢谢^^

也可以关注我，每日分享题解，一起刷题，一起拿全家桶。