LeetCode_143_DeleteOperationForTwoStrings

1. question: 两个字符串的删除操作（中等）

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-operation-for-two-strings

示例 1：

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

示例 2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

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

2. answers

这道题，意思就是每个字符串中都可删除一定数量的字母，使得形成两个相同的单词。要求，删除的字符最少。

既然最终形成的单词相同，那么就是公共子序列，同时删除的字符最少，即剩余的字符最多，也就是最长公共子序列。最终删除的字符数量就是：总长度-2*公共子序列长度。

代码如下所示：

public class Solution_0143 {

    public int minDistance(String word1, String word2) {

        int[][] dp = new int[word1.length()][word2.length()];

        // 初始化
        if(word1.charAt(0) == word2.charAt(0)) dp[0][0] = 1;
        else dp[0][0] = 0;

        for (int i = 1; i < word2.length(); i++) {
            if(word1.charAt(0) == word2.charAt(i)) dp[0][i] = 1;
            else dp[0][i] = dp[0][i-1];
        }

        for (int i = 1; i < word1.length(); i++) {
            if(word2.charAt(0) == word1.charAt(i)) dp[i][0] = 1;
            else dp[i][0] = dp[i-1][0];
        }

        // 动态规划
        for (int i = 1; i < word1.length(); i++) {
            for (int j = 1; j < word2.length(); j++) {

                if(word1.charAt(i) == word2.charAt(j)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }

        return word1.length() + word2.length() - 2 * dp[word1.length()-1][word2.length()-1];
    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0143 s = new Solution_0143();

//        String word1 = "sea";
//        String word2 = "eat";

        String word1 = "leetcode";
        String word2 = "etco";

        System.out.println(s.minDistance(word1, word2));
    }
}

除了上面最长公共子序列的思路，其实这相当于是编辑距离问题，可以从删除字符的角度看待本问题。

设字符串word1[0:i]，字符串word2[0:j]，如果word1[0:i]和字符串word2[0:j]相同所需的最少操作次数为dp[i][j]。

那么字符串word1[0:i+1]和字符串word2[0:j+1]相同所需的最少操作次数该怎么做呢？

1. 如果word1[i+1]和word2[j+1]相同的话，显然操作次数和前面的一样，即dp[i+1][j+1]=dp[i][j]
2. 如果不同，此时可有三种选择：
   1. 删除word1[i+1]，dp[i+1][j+1]=dp[i][j+1] + 1
   2. 删除word2[i+1]，dp[i+1][j+1]=dp[i+1][j] + 1
   3. 二者都删除，dp[i+1][j+1]=dp[i][j] + 2

在删除这里可能有疑问，可逐个字符遍历尝试一下。两个字符都是从前向后逐步遍历的。

代码如下所示：

 /**
 * 以编辑距离的思路做一下这道题。
 *
 * 题目中要求通过删除字符来使得二者达到相同。
 *
 * 如果word1[i]和word2[j]相同，显然，因为是最小步数，二者一定不需要删除。那么到达此处时的总步数，一定就等于到达word1[i-1]、word2[j-1]时的步数
 *
 * 如果二者不同，那么:
 *      1. word1[i-1]和word2[j]相同，删掉word1[i]即可。dp[i-1][j] + 1
 *      2. word1[i]和word2[j-1]相同，删掉word2[i]即可。dp[i][j-1] + 1
 *      3. 上面都不同，即删掉两个元素。dp[i-1][j-1] + 2
 *      4. 上述三者取最小即可
 *
 *  因此，定义数组dp[i][j]，表明以word1[0:i]和word2[0:j]为止的两个单词相同，所需要的最少步数
 *  之后，如果word1[i+1] 和 word2[j+1]进行比较。
 */
public class Solution_0143_02 {

    public int minDistance(String word1, String word2) {

        // 定义数组
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        // 初始化，即word1为空时，word2[i]所需操作的步数
        for (int i = 0; i < word2.length() + 1; i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i < word1.length() + 1; i++) {
            dp[i][0] = i;
        }

        // 动态规划
        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {

                // 此时i和j是数组中的下标，注意其与字符串下标的关系
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = Math.min(Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + 2);
            }
        }

        return dp[word1.length()][word2.length()];
    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0143_02 s0143 = new Solution_0143_02();

//        String word1 = "sea";
//        String word2 = "eat";

        String word1 = "leetcode";
        String word2 = "etco";

        System.out.println(s0143.minDistance(word1, word2));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。