LeetCode刷题实战583：两个字符串的删除操作

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 两个字符串的删除操作，我们先来看题面：

https://leetcode-cn.com/problems/delete-operation-for-two-strings/

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.

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

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

示例

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

示例 2:
输入：word1 = "leetcode", word2 = "etco"
输出：4

解题

https://blog.csdn.net/hequnwang10/article/details/123941103

主要思路：动态规划

dp[i][j]：表示要使word1和word2变成下标为i和j时相等的字符串需要最少的删除次数

初始化：

当word1字符串为空时，需要将word2字符串依次删除才可以：

dp[0][j]=j

同样的，当word2字符串为空时，需要将word1字符串依次删除才可以：

dp[i][0]=i

当两者都不为空时，从第一个字符开始遍历，要么两个字符相等，要么两个字符不相等：

两个字符相等时，直接与上一个状态相等

dp[i][j] = dp[i – 1][j – 1]

两个字符不相等时，则由上一个状态转移，找最小的删除次数，然后+1；

dp[i][j] = Math.min(dp[i – 1][j], dp[i][j – 1]) + 1;

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        //当一个字符串为空时，如果需要两个字符串都相同，必须将另一个字符串全部删除
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        //当一个字符串为空时，如果需要两个字符串都相同，必须将另一个字符串全部删除
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            char c1 = word1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = word2.charAt(j - 1);
                //如果两个字符串的字符相等，则最少删除次数不变。
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //如果两个字符串的字符不相等，则取两个字符串减一个后的最小值 然后+1。
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}