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

给定两个单词 word1word2 ,返回使得 word1word2 相同所需的最小步数

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

示例 1:

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

示例 2:

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

提示:

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

算法思路:

考虑动态规划,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.


以无限为有限,以无法为有法