本文目录
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. 编辑距离
做题
无思路。
看文章
前期的铺垫都是为了这道题。
动规五部曲：
-
确定dp数组（dp table）以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
-
确定递推公式
编辑的几种操作：
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几种操作取最小，就是递推公式。
-
dp数组如何初始化
dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。
那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i; 同理dp[0][j] = j; -
确定遍历顺序
-
举例推导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。
心得：编辑距离总结，把两字符之间的增删改解决了。
标签：随想录,距离,编辑,range,word1,len,word2,字符串,dp From： https://blog.csdn.net/Xiu_Yuan123/article/details/139317764