Java描述 LeetCode，583. Delete Operation for Two Strings

Java描述 LeetCode，583. Delete Operation for Two Strings

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力。

1-1：题目

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Example 1:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Example 2:

Input: word1 = "leetcode", word2 = "etco"
Output: 4

Constraints:

1 <= word1.length, word2.length <= 500
word1 and word2 consist of only lowercase English letters.

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

1-2：idea 1-2-1：问题转换的思想

两个字符串word1，word2，要删除字符使他们变成相同的字符，要尽量少删，意思就是尽量保持最多相同的字符，也就是最长相同字串，这样删除的就少了，题目也就变成了Java描述 LeetCode，1143. Longest Common Subsequence，这道题。找出了最长相同子串，就好办了。相关题解请看。https://blog.csdn.net/qq_41376740/article/details/121248624。

1-2-2：代码

public static int minDistance(String word1, String word2) {
    int n = word1.length();
    int m = word2.length();

    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; 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]);
            }
        }
    }
    System.out.println(Arrays.deepToString(dp));
    return n + m - 2 * dp[n][m];
}

1-2-3：直接做

• 确定状态：dp[i][j] 以word1[i]结尾的子串word1[0:i] 和 word2[j]结尾的子串word2[0:j] 变成相同的字符串需要删除dp[i][j个字符。这个和之前的差不多，很好理解。
• 状态转移方程：
  • 当 word1[i] != word2[j]，不相等的时候有三个选择，删除当中的一个，word1[i] 或者 word2[j] 两个都删掉，三种选择取最小值，dp[i][j] = min(dp[i-1][j] + 1,dp[i][j-1] + 1, dp[i-1][j-1] + 2)；
  • 当word1[i] == word2[j]；dp[i][j] = dp[i][j] = dp[i - 1][j - 1]；
• 初始化，处理边界：第0行和第0列，分别代表空字符串，空字符串和任何字符串要变成相同，只有将另一个字符串的字符全部删除；
• 确定遍历顺序。

1-2-4：代码

public static int minDistance2(String word1, String word2) {
    int n = word1.length();
    int m = word2.length();

    int[][] dp = new int[n + 1][m + 1];

    for (int i = 0; i <= m; i++) {
        dp[0][i] = i;
    }
    for (int j = 0; j <= n; j++) {
        dp[j][0] = j;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + 2);
            } else {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    System.out.println(Arrays.deepToString(dp));
    return dp[n][m];
}
     e  t  c  o
 [0, 1, 2, 3, 4], 
l[1, 2, 3, 4, 5], 
e[2, 1, 2, 3, 4], 
e[3, 2, 3, 4, 5], 
t[4, 3, 2, 3, 4], 
c[5, 4, 3, 2, 3], 
o[6, 5, 4, 3, 2], 
d[7, 6, 5, 4, 3], 
e[8, 7, 6, 5, 4]

1-3：总结

这道题不难的，如果做了最长相同子序列，还是很好做的。或者有，之前几道题的思想，直接做也是可以做出来的。今天成功AC两题，nice，虽然都是有前几天的题目铺垫而来，但是还是很成功的。不会写的可以看一下之前的几道题。继续加油啊！河海哥，冲！如有错误还请指正，不胜感激，你的赞和评论是我最大的动力。一起加油！