网站建设公司济南,oa软件有哪些公司,企业网站硬件设计,wordpress调用分类描述Leetcode - 583dp[i][j]代表以i-1结尾的words1的子串 要变成以j-1结尾的words2的子串所需要的次数。初始化#xff1a; 变成 所需0次 dp[0][0] 0, 变成words2的子串 需要子串的长度的次数,所以dp[0][j] j, 同理#xff0c;dp[i][0] …Leetcode - 583dp[i][j]代表以i-1结尾的words1的子串 要变成以j-1结尾的words2的子串所需要的次数。初始化 变成 所需0次 dp[0][0] 0, 变成words2的子串 需要子串的长度的次数,所以dp[0][j] j, 同理dp[i][0] i.递推 若words1[i-1] words2[j-1]则不需要做任何操作 dp[i][j] dp[i-1][j-1].若不等值为words1或者words2中删除一个字符完成两个字符串相等的最小操作数dp[i][j] min(dp[i-1][j] 1,dp[i][j-1] 1) 因为进行了一次删除操作所以是1.def minDistance(self, word1: str, word2: str) - int:dp [[0 for _ in range(len(word2)1) ] for _ in range(len(word1)1)]for i in range(1,len(word1) 1):dp[i][0] ifor i in range(1,len(word2)1):dp[0][i] ifor 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)return dp[-1][-1]Leetcode - 72dp[i][j]定义以及初始化都与上一题一致没有区别。区别在于递推1若相等则不用做操作直接dp[i][j] dp[i-1][j-1]2.若不等则这是重头戏首先是两边各删一个字符的两种情况但是注意其实这里包含了四种情况以words1[i-1],words2[j-1]为结尾的两个串dp[i-1][j],dp[i][j-1]分别代表在这个基础上删除了一个字符但是以words[i-2],words[j-2]的视角出发dp[i-1][j],dp[i][j-1]分别代表在这个基础上分别增添了一个字符可以认为一个串增添了一个字符就代表另一个串少了一个字符。 所以这里是包含了四种情况。 那么替换的情况就是 dp[i-1][j-1] 1即可在原来的基础上增添一次替换def minDistance(self, word1: str, word2: str) - int:dp [[0 for _ in range(len(word2)1) ] for _ in range(len(word1)1)]for i in range(1,len(word1) 1):dp[i][0] ifor i in range(1,len(word2)1):dp[0][i] ifor 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]1)return dp[-1][-1]
