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

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

代码随想录：583. 两个字符串的删除操作
Leetcode：583. 两个字符串的删除操作

做题

找出最长公共子序列，然后用两个字符串的长度和减去两倍最长公共子序列长度即可。

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(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] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return len(word1) + len(word2) - 2 * dp[len(word1)][len(word2)]

时间复杂度: O(n * m)
空间复杂度: O(n * m)

看文章

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

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] + 2, dp[i-1][j] + 1, dp[i][j-1] + 1)
        return dp[-1][-1]

时间复杂度: O(n * m)
空间复杂度: O(n * m)

72. 编辑距离

代码随想录：72. 编辑距离
Leetcode：72. 编辑距离

做题

无思路。

看文章

前期的铺垫都是为了这道题。
动规五部曲：

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

   dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

2. 确定递推公式

   编辑的几种操作：

   if (word1[i - 1] == word2[j - 1])
       不操作
   if (word1[i - 1] != word2[j - 1])
       增
       删
       换
   

   增、删：dp[i][j] = dp[i - 1][j] + 1、dp[i][j] = dp[i][j - 1] + 1
   换：dp[i][j] = dp[i - 1][j - 1] + 1

   几种操作取最小，就是递推公式。

3. dp数组如何初始化

   dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。
   那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i; 同理dp[0][j] = j;

4. 确定遍历顺序

5. 举例推导dp数组

具体代码如下：

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]

时间复杂度: O(n * m)
空间复杂度: O(n * m)

编辑距离总结篇

代码随想录：编辑距离总结篇

以往忽略的知识点小结

• 编辑距离是最后的汇总题，包含增、删、改这三种操作，增删可以理解为同一种

个人体会

完成时间：1h30min。
心得：编辑距离总结，把两字符之间的增删改解决了。

​