代码随想录算法训练营Day56 | 583. 两个字符串的删除操作 | 72. 编辑距离 | 编辑距离总结篇

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

题目链接 | 解题思路

本题的第一反应应该是进行最长公共子序列的抽象化，因为删除元素这个操作看上去很复杂。但实际上，也能通过 dp 来记录删除操作，也为后面那道编辑距离打下了基础。

抽象化：最长公共子序列的长度

从两个不同的字符串删除元素直到相同，也可以理解为找到最长公共子序列之后就删除多余的元素。这样的抽象化后，可以直接套用找最长公共子序列的解法，在最后用两个字符串的总长度减去两倍的最长公共子序列长度即可。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * len(word2) for _ in range(len(word1))]

        first_row_flag = first_col_flag = False
        for j in range(len(word2)):
            if word1[0] == word2[j]:
                first_row_flag = True
            if first_row_flag:
                dp[0][j] = 1
        for i in range(len(word1)):
            if word1[i] == word2[0]:
                first_col_flag = True
            if first_col_flag:
                dp[i][0] = 1
        
        for i in range(1, len(word1)):
            for j in range(1, len(word2)):
                if word1[i] == word2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    
        return len(word1) + len(word2) - 2 * dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

dp 记录删除元素的数量

删除元素看着很复杂，因为从结果上来看，删除这个步骤可以发生在任一字符串的任一位置，没办法通过 dp 找到规律。但实际上，只要在 dp 的递推中正确递推了最优解，那就可以解题。

初始化终于变的复杂了，不能再直接初始化第一行和第一列。对于这样的数据，构造对应 "" 的第0行和第0列才是正道！

1. dp 数组的下标含义：dp[i][j] 是 word1[:i] 和 word2[:j] 能够达到相同需要的最少删除数（这里定义的改变和后面的）
2. dp 递推公式：
   • 如果 word1[i] == word2[j]，那么不需要对这两个尾部元素进行任何删除，dp[i][j] = dp[i-1][j-1]
   • 否则，必然要至少删掉一个元素才能使得有可能使得两个字符串能够匹配，所以 dp[i][j] = min(dp[i-1][j], dp[i][j-1])
     • 注意，当然有可能这两个尾部元素都需要删除，但这个情况 dp[i-1][j-1] + 2 被包含在了 dp[i-1][j], dp[i][j-1] 中，可以不需要额外考虑
3. dp 的初始化：
   • 对于 word1="" 来说，需要删除 word2[:j] 中所有的元素才行，也就是 dp[0][j] = j
   • 同理，dp[i][0] = i
4. dp 遍历顺序：从上到下、从左到右即可
5. 举例推导：word1 = "sea", word2 = "eat"

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]

        for i in range(len(word1) + 1):
            dp[i][0] = i
        for j in range(len(word2) + 1):
            dp[0][j] = j
        
        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1
        
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

72. 编辑距离

题目链接 | 解题思路

1. dp 数组的下标含义：dp[i][j] 是将 word1[:i] 转换成 word2[:j] 的最少操作数（定义和初始化有点关系，类似于背包问题）

2. dp 递推公式：

   • 如果 word1[i-1] == word2[j-1]，那么各自的结尾元素不需要进行任何操作，直接转换成之前的子问题，dp[i][j] = dp[i-1][j-1]
   • 否则，我们显然需要进行一次操作（insert、delete、change）才能转换成之前的子问题
     • 如果需要进行 insert，显然我们是希望在 word1[:i] 的后面加上一个 word2[i-1]，这样将当前问题转换成了子问题：“将 word1[:i] 转换成 word2[:j-1]”，dp[i][j] = dp[i][j-1] + 1
     • 如果需要进行 delete，显然我们是希望删除 word1[i-1]，这样将当前问题转换成了子问题：“将 word1[:i-1] 转换成 word2[:j]”，dp[i][j] = dp[i-1][j] + 1
     • 如果需要进行 change，显然我们是希望将 word1[i-1] 变成 word2[j-1]，这样将当前问题转换成了子问题：“将 word1[:i-1] 转换成 word2[:j-1]”，dp[i][j] = dp[i-1][j-1] + 1
   • 由于我们需要记录最小操作数，所以 dp[i][j] = min([dp[i-1][j-1], dp[i-1][j], dp[i][j-1]]) + 1

3. dp 数组的初始化：本题如果直接进行第一行和第一列的初始化，难度无疑逆天，所以才用了背包问题一样处理 "" 的定义来帮助初始化

   • 对于 i=0 (word1 = "")，将其转化成 word2[:j] 显然需要 j 次操作（insert），所以 dp[0][j] = j
   • 对于 j=0 (word2 = "")，将 word2[:i] 其转化成 "" 显然需要 i 次操作（delete），所以 dp[i][0] = i
   • 这样的初始化比真正处理长度为 1 的 word1, word2 要正常多了

4. dp 的遍历顺序：递推依赖左上方的元素，从上到下、从左到右即可

5. 举例说明：word1 = "horse", word2 = "ros"

   	''	r	o	s
   ''	0	1	2	3
   h	1	1	2	3
   o	2	2	1	2
   r	3	2	2	2
   s	4	3	3	2
   e	5	4	4	3

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]

        for i in range(len(word1) + 1):
            dp[i][0] = i
        for j in range(len(word2) + 1):
            dp[0][j] = j
        
        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min([dp[i-1][j-1], dp[i][j-1], dp[i-1][j]]) + 1
        
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

编辑距离总结篇

编辑距离总结

在之前的讲解中，或多或少提到了编辑距离。那些题目或多或少都有一些别的解法，或者看作是重复字数组、重复子序列的变种。但是，实际上他们都能被看作是编辑距离这个终极版本的削弱版本：

• 判断子序列 可以看作：只允许删除 t 的元素的情况下能否得到 s
• 不同的子序列 可以看作：有多少种删除 t 的元素的方法能够得到 s
• 两个字符串的删除操作 可以看作：允许删除两个字符串的元素，使其相同所需要的最少操作数
• 编辑距离 就是真正的编辑距离