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

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

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

示例 1：

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

示例 2:

输入：word1 = “leetcode”, word2 = “etco”
输出：4

提示：

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

算法思路：

考虑动态规划，dp[i][j] 表示 以i-1为结尾的字符串word1，和以 j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少步数。递推公式如下：

• 比较 word[i - 1] 和 word[j - 1]，

  • 如果相等，则不需要删除，为 dp[i][j] = dp[i - 1][j - 1];

  • 不相等，则需要删除，分三个情况

    • 删 word1，则为 dp[i - 1][j] + 1
    • 删 word2，则为 dp[i][j - 1] + 1
    • 都删，则为 dp[i - 1][j - 1] + 2

    所以取这三种情况中最小的那个。

代码实现：

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length(), len2 = word2.length();
        //以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，
        // 想要达到相等，所需要删除元素的最少次数
        int[][] dp = new int[len1 + 1][len2 + 1];
        // 两者有一个为空则所需步数为另一个的长度
        for (int i = 0; i <= word1.length(); i++) dp[i][0] = i;
        for (int j = 0; j <= word2.length(); j++) dp[0][j] = j;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // 相等则不需要删
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 不相等：
                    // 1.删 word1：dp[i - 1][j] + 1
                    // 2.删 word2：dp[i][j - 1] + 1
                    // 3.都删：dp[i - 1][j - 1] + 2
                    dp[i][j] = Math.min(dp[i - 1][j] + 1,
                            Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2));
                }
            }
        }
        return dp[len1][len2];
    }

Q.E.D.