Leetcode 72.编辑距离

注意的点：

1、边界条件需要限定到:j+1 or : i+1

解法：动态规划

DP法

classSolution:defminDistance(self,word1:str,word2:str)->int:n,m=len(word1),len(word2)ifn==0orm==0:returnmax(m,n)dp=[[0]*mfor_inrange(n)]# 得行和列分别初始化，这块最难foriinrange(n):dp[i][0]=i+1-int(word2[0]inword1[:i+1])forjinrange(m):dp[0][j]=j+1-int(word1[0]inword2[:j+1])foriinrange(1,n):forjinrange(1,m):ifword1[i]==word2[j]:dp[i][j]=dp[i-1][j-1]else:dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1returndp[n-1][m-1]

递归法

classSolution:defminDistance(self,word1:str,word2:str)->int:ifnotword1ornotword2:returnlen(word1)+len(word2)@cachedefdp(i,j):ifi==0:returnj+1-int(word1[0]inword2[:j+1])ifj==0:returni+1-int(word2[0]inword1[:i+1])ifword1[i]==word2[j]:returndp(i-1,j-1)else:returnmin(dp(i-1,j-1),dp(i,j-1),dp(i-1,j))+1# 对应了三类操作returndp(len(word1)-1,len(word2)-1)