当前位置：首页 > article >正文

力扣583-两个字符串的删除操作（Java详细题解）

article 2024/9/27 11:14:07

题目链接：两个字符串的删除操作

前情提要：

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组利于debug。

每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。

题目思路:

本题的题目描述非常清晰，要求使word1和word2相同的最少删除次数。

是不是跟不同的子序列这道题很像，只不过不同子序列是求删除s中的元素出现t的次数。只删除s中的元素。

而本题是可以删除俩个字符串的元素。

话不多说，直接开始dp五部曲吧。

1.确定dp数组和i下标的含义。

dp[i] [j] 是指以i - 1为结尾的word1和以j - 1为结尾的word2相同所需要删除元素的最少次数。

注意这里是以i - 1为结尾，j - 1为结尾。至于为什么要这样设置dp数组看看我这篇题解力扣718-最长重复子数组（Java详细题解）-CSDN博客。

2.确定递推公式。

子序列问题都要考虑word1[i - 1] 是否等于 word2[j - 1]的情况。

相等的情况。

既然最后结尾的元素相等，那么就要在以前一个为结尾的元素的字符串中删除了。

所以dp[i] [j] = dp[i - 1] [j - 1]；
不相等的情况

不相等我们就要删除元素了，具体的删除情况有三种。
1. 删除nums[i - 1]
2. 删除nums[j - 1]
3. 俩个同时删
  
  具体我们取哪个呢？注意题目要求最少次数，所以我们要对这三个取一个最小值。
  
  dp[i] [j] = Math.min(dp[i - 1] [j] + 1,Math.min(dp[i] [j - 1] + 1,dp[i - 1] [j - 1] + 2);
小拓展：

其实这里可以不用比较俩个都删的情况，因为前俩种情况都包含进去了。怎么理解呢？

dp[i - 1] [j] 其实就是删除word1[i - 1]元素后需要删除元素的最少次数。

那么让他再加1，就表示此时删word2[j - 1]。是不是就是俩个元素全删的情况，即dp[i - 1] [j] + 1

所以dp[i] [j] =Math.min(dp[i - 1] [j] + 1,dp[i] [j - 1] + 1);

如果不理解这个没关系，记住我上一个版本就好。

3.dp初始化。

由递推公式可以看出dp[i] [j] 是由dp[i] [j - 1]或者dp[i - 1] [j]或dp[i - 1] [j - 1]推出。

所以在二维dp数组里就由他的上方左方和左上方三个方向推出。

那么起始位置就是第一行和第一列；

dp[i] [0] dp[0] [j] 指的是空串和另一个字符串相同时删除的最少次数。

那么使他们相同最少删除次数就是让有元素的字符串的元素全部删掉。

所以dp初始化为

for(int i = 0;i <= s.length();i ++){
            dp[i][0] = i;
        }
        for(int i = 0;i <= t.length();i ++){
            dp[0][i] = i;
        }

4.确定dp的遍历顺序。

由递推公式可以看出dp[i] [j] 是由dp[i] [j - 1]或者dp[i - 1] [j]或dp[i - 1] [j - 1]推出。

所以在二维dp数组里就由他的上方左方和左上方三个方向推出。

所以遍历顺序一定是从左到右，从上到下。

5.如果没有ac打印dp数组利于debug。

在这里插入图片描述

最终代码：

class Solution {
    public int minDistance(String s, String t) {
        //dp定义
        int [][] dp =new int [s.length() + 1][t.length() + 1];
        //初始化
        for(int i = 0;i <= s.length();i ++){
            dp[i][0] = i;
        }
        for(int i = 0;i <= t.length();i ++){
            dp[0][i] = i;
        }
        //遍历顺序
        for(int i = 1;i <= s.length();i ++){
            for(int j = 1;j <= t.length();j ++){
                //递推公式
                if(s.charAt(i - 1) == t.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    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[s.length()][t.length()];
    }
}