583 两个字符串的删除操作（动态规划-递推）

怼烎@ 2022-08-31 12:22 162阅读 0赞

**1. 问题描述：**

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

**示例：**

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

**提示：**

给定单词的长度不超过500。  
给定单词中的字符只含有小写字母。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/delete-operation-for-two-strings

**2. 思路分析：**

分析题目可以知道我们需要删除word1和word2中的某些字符使得word1和word2中剩余的字符相同，并且删除的操作次数是最少的，所以我们需要使得剩余的相同字符数目是最大的，所以本质上求解的是**最长公共子序列**问题，所以我们可以使用最长公共子序列的方法进行求解。除了这个方法之外，我们还可以直接分析进行求解，也即直接使用动态规划的递推思路求解，因为涉及到两个字符串所以定义状态表示的时候我们需要定义二维的dp数组，我们可以定义dp\[i\]\[j\]为将word1\[1:i\]和word2\[1:j\]变成相同字符串所需要的最少步数，这个定义其实很直观，直接根据题目的表达的意思进行定义的，那么怎么样进行状态计算呢？可以发现对于dp\[i\]\[j\]我们可以根据最后一个字符是否剩余来分成若干类（对应若干个不同的集合），根据最后一个字符是否剩余那么就可以将dp\[i\]\[j\]分为四类进行状态计算，由之前四个可能的状态转移到当前的状态：

*  i，j对应的字符都在
 *  i对应的字符在，j对应的字符不在
 *  i对应的字符不在，j对应的字符在
 *  i，j对应的字符都不在

其中对于第一类有dp\[i - 1\]\[j - 1\]，但是这一类存在有一个前提是word1\[i\] = word2\[j\]，对于第二类，有dp\[i\]\[j - 1\] + 1，对于第三类也是类似的，有 dp\[i - 1\]\[j\] + 1，对于第四类有dp\[i - 1\]\[j - 1\] + 2，可以发现对于第四类的状态计算包括在第二类和第三类中所以在状态计算的时候可以不用考虑第四类（考虑也没关系），例如对于考虑第二类的时候也会考虑四大类这样就会考虑到第四类的情况。主要理解动态规划中递推的过程。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

class Solution:
        # 动态规划
        def minDistance(self, word1: str, word2: str) -> int:
            n, m = len(word1), len(word2)
            dp = [[0] * (m + 1) for i in range(n + 1)]
            # 初始状态将s2[1:i]的字符变成s1[0]一样需要得到操作表示删除掉s2中的所有字符的操作次数
            for i in range(1, m + 1):
                dp[0][i] = i
            # 初始状态将s1[1:i]的字符变成s2[0]一样需要得到操作表示删除掉s1中的所有字符的操作次数
            for i in range(1, n + 1):
                dp[i][0] = i
            for i in range(1, n + 1):
                for j in range(1, m + 1):
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
                    # 判断i,j都在的情况, 因为这一类可能不存在
                    if word1[i - 1] == word2[j - 1]:
                        dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
            return dp[n][m]

**最长公共子序列思路：**

class Solution:
        # 动态规划
        def minDistance(self, word1: str, word2: str) -> int:
            n, m = len(word1), len(word2)
            dp = [[0] * (m + 1) for i in range(n + 1)]
            for i in range(1, n + 1):
                for j in range(1, m + 1):
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                    if word1[i - 1] == word2[j - 1]:
                        dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)
            # 返回需要删除的最少的次数
            return n + m - 2 * dp[n][m]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/c8851a0e6f734ece9641792330769a31.png