583. 两个字符串的删除操作

刺骨的言语ヽ痛彻心扉 2023-10-16 17:57 7阅读 0赞

#### 583. 两个字符串的删除操作 ####

*  题干分析
 *  解题思路
 *   *  动态规划一
     *   *  1. 确定dp数组（dp table）以及下标的含义
         *  2. 确定递推公式
         *  3. dp数组如何初始化
         *  4. 确定遍历顺序
         *  5. 举例推导dp数组
     *  动态规划二
 *  代码实现

## 题干分析 ##

[力扣入口][Link 1]

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

*  输入: “sea”, “eat”
 *  输出: 2
 *  解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

## 解题思路 ##

### 动态规划一 ###

本题和**动态规划：115.不同的子序列** 相比，其实就是两个字符串都可以删除了，情况虽说复杂一些，但整体思路是不变的。

这次是两个字符串可以相互删了，这种题目也知道用动态规划的思路来解，动规五部曲，分析如下：

#### 1. 确定dp数组（dp table）以及下标的含义 ####

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

这里dp数组的定义有点点绕，大家要撸清思路。

#### 2. 确定递推公式 ####

*  当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\]不相同的时候，有三种情况：

1.  情况一：删word1\[i - 1\]，最少操作次数为dp\[i - 1\]\[j\] + 1
2.  情况二：删word2\[j - 1\]，最少操作次数为dp\[i\]\[j - 1\] + 1
3.  情况三：同时删word1\[i - 1\]和word2\[j - 1\]，操作的最少次数为dp\[i - 1\]\[j - 1\] + 2

那最后当然是取最小值，所以当word1\[i - 1\] 与 word2\[j - 1\]不相同的时候，递推公式：dp\[i\]\[j\] = min(\{dp\[i - 1\]\[j - 1\] + 2, dp\[i - 1\]\[j\] + 1, dp\[i\]\[j - 1\] + 1\});

因为 dp\[i\]\[j - 1\] + 1 = dp\[i - 1\]\[j - 1\] + 2，所以递推公式可简化为：dp\[i\]\[j\] = min(dp\[i - 1\]\[j\] + 1, dp\[i\]\[j - 1\] + 1);

从字面上理解 就是 当 同时删word1\[i - 1\]和word2\[j - 1\]，dp\[i\]\[j-1\] 本来就不考虑 word2\[j - 1\]了，那么再删 word1\[i - 1\]，是不是就达到两个元素都删除的效果，即 dp\[i\]\[j-1\] + 1。

#### 3. dp数组如何初始化 ####

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

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

dp\[0\]\[j\]的话同理。

#### 4. 确定遍历顺序 ####

从递推公式 dp\[i\]\[j\] = min(dp\[i - 1\]\[j - 1\] + 2, min(dp\[i - 1\]\[j\], dp\[i\]\[j - 1\]) + 1); 和dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\]可以看出dp\[i\]\[j\]都是根据左上方、正上方、正左方推出来的。

所以遍历的时候一定是从上到下，从左到右，这样保证dp\[i\]\[j\]可以根据之前计算出来的数值进行计算。

#### 5. 举例推导dp数组 ####

以word1:“sea”，word2:"eat"为例，推导dp数组状态图如下：  
![在这里插入图片描述][17acce2df1294b0e95120dc7ff0803aa.png]

### 动态规划二 ###

本题和**动态规划：1143.最长公共子序列** 基本相同，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

## 代码实现 ##

class Solution {
        
       // 583.两个字符串的删除操作 - dp数组中存储word1和word2最长相同子序列的长度
        public int minDistance(String word1, String word2){
        
            int len1 = word1.length();
            int len2 = word2.length();
            int[][] dp = new int[len1 + 1][len2 + 1];
    
            for(int i = 1; i <= len1; i++){
        
                for(int j = 1; j <= len2; 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]);
                    }
                }
            }
            return len1 + len2 - dp[len1][len2] * 2;
        }
    }

**参考资料**：[代码随想录-583. 两个字符串的删除操作][-583.]

[Link 1]: https://leetcode.cn/problems/delete-operation-for-two-strings/
[17acce2df1294b0e95120dc7ff0803aa.png]: https://img-blog.csdnimg.cn/17acce2df1294b0e95120dc7ff0803aa.png
[-583.]: https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE