两个字符串的删除操作

583. 两个字符串的删除操作 - 力扣（LeetCode）

给定两个单词 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数组（dp table）以及下标的含义

dp[i] [j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

确定递推公式

• 当word1[i - 1] 与 word2[j - 1]相同的时候
• 当word1[i - 1] 与 word2[j - 1]不相同的时候

当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i] [j] = dp[i - 1] [j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候，：

情况一：删word1[i - 1]，最少操作次数为dp[i - 1] [j] + 1

情况二：删word2[j - 1]，最少操作次数为dp[i] [j - 1] + 1

此处删除与添加的作用相同，可以理解为去掉word1[i-1]或word2[j-1]最后一位的最少次数，再添加一次元素

即删除word1[i-1]或删除word2[j-1]后的状态添加一个字符即可的得到dp[i] [j]的状态

在本题中，删除操作和添加操作等效，只要到的得到两个相同的字串即可，所有可以看作添加操作也为一步

dp数组如何初始化

从递推公式中，可以看出来，dp[i] [0] 和 dp[0] [j]是一定要初始化的。

dp[i] [0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i] [0] = i。

class Solution {
    public int minDistance(String word1, String word2) {
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int len1 = chars1.length;
        int len2 = chars2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];

        //dp[i][j]表示以i-1结尾的word1变成以j-1为结尾的word2的最小步数
        for(int i = 0; i <= len1; i++){
            dp[i][0] = i;     //长度为i的words1要删除i次变成空字符串
        }
        for(int j = 0; j <= len2; j++){
            dp[0][j] = j;     //长度为i的word2要删除i次变为空字符串
        }
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(chars1[i-1] == chars2[j-1]){ //不需要删除
                    dp[i][j] = dp[i-1][j-1];
                }else{ //删除words1[i-1]或删除words2[j-1]的状态增加一个字符得到dp[i][j]
                    dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1);
                }
            }
        }
        return dp[len1][len2];
    }
}

方法二：

直接求出两个数组的最大公共子序列，除了最大公共子序列，都是要删除的字符

所以删除的步数为len1 + len2 - 最大公共子序列长度*2

class Solution {
    public int minDistance(String word1, String word2) {
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int len1 = chars1.length;
        int len2 = chars2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];

        //dp[i][j]表示以i-1结尾的word1变成以j-1为结尾的word2的最大公共子序列
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(chars1[i-1] == chars2[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 len1 + len2  -  2 * dp[len1][len2];
    }
}