学院网站建设需求分析调研表,学校网站内容,网站广告js代码添加,福州网签Day 56
583. 两个字符串的删除操作
dp[i][j]#xff1a;以i-1为结尾的字符串word1#xff0c;和以j-1位结尾的字符串word2#xff0c;想要达到相等#xff0c;所需要删除元素的最少次数。
当word1[i - 1] 与 word2[j - 1]相同的时候,dp[i][j] dp[i - 1][j - 1];当word1…Day 56
583. 两个字符串的删除操作
dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。
当word1[i - 1] 与 word2[j - 1]相同的时候,dp[i][j] dp[i - 1][j - 1];当word1[i - 1] 与 word2[j - 1]不相同的时候
情况一删word1[i - 1]最少操作次数为dp[i - 1][j] 1
情况二删word2[j - 1]最少操作次数为dp[i][j - 1] 1
情况三同时删word1[i - 1]和word2[j - 1]操作的最少次数为dp[i - 1][j - 1] 2
dp[i][0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。
dp[0][j]的话同理
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] ifor j in range(len(word2) 1):dp[0][j] jfor 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]1, dp[i-1][j-1]2)return dp[-1][-1]
72. 编辑距离
dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。
if (word1[i - 1] word2[j - 1]) 那么说明不用任何编辑dp[i][j] 就应该是 dp[i - 1][j - 1]即dp[i][j] dp[i - 1][j - 1];此时可能有同学有点不明白为啥要即dp[i][j] dp[i - 1][j - 1]呢
那么就在回顾上面讲过的dp[i][j]的定义word1[i - 1] 与 word2[j - 1]相等了那么就不用编辑了以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1]就是 dp[i][j]了。
在下面的讲解中如果哪里看不懂就回想一下dp[i][j]的定义就明白了。
在整个动规的过程中最为关键就是正确理解dp[i][j]的定义
if (word1[i - 1] ! word2[j - 1])此时就需要编辑了如何编辑呢
操作一word1删除一个元素那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] dp[i - 1][j] 1;
操作二word2删除一个元素那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] dp[i][j - 1] 1;
这里有同学发现了怎么都是删除元素添加元素去哪了。
word2添加一个元素相当于word1删除一个元素例如 word1 ad word2 aword1删除元素d 和 word2添加一个元素d变成word1a, word2ad 最终的操作数是一样
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] ifor j in range(len(word2) 1):dp[0][j] jfor 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-1][j], dp[i][j-1]) 1return dp[-1][-1]
