同样这一题还是利用动态规划的思想解决,三种方法如下：
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
#纯递归不通过，时间复杂度过高
# def dp(i,j):
# if i == -1:
# return j+1
# if j==-1:
# return i+1
# if word1[i]==word2[j]:
# return dp(i-1,j-1)
# else:
# return min(dp(i,j-1)+1,dp(i-1,j)+1,dp(i-1,j-1)+1)
# return dp(m-1,n-1)
#备忘录解决，通过
# memo = dict()
# def dp(i,j):
# if (i,j) in memo:
# return memo[(i,j)]
# if i == -1:
# return j+1
# if j==-1:
# return i+1
# if word1[i]==word2[j]:
# memo[(i,j)]=dp(i-1,j-1)
# else:
# memo[(i,j)] = min(dp(i,j-1)+1,dp(i-1,j)+1,dp(i-1,j-1)+1)
# return memo[(i,j)]
# return dp(m-1,n-1)
#DP table 解决自底向上
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(m+1):
dp[0][i]=i
for j in range(n+1):
dp[j][0]=j
for i in range(1,n+1):
for j in range(1,m+1):
if word1[j-1]==word2[i-1]:
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j-1]+1,dp[i-1][j]+1)
return dp[n][m]
上述代码中要特别注意的就是行列的n,m
