Leetcode刷题记录——72. 编辑距离
程序员文章站
2022-04-18 09:24:52
设word1的长度是mword2的长度是ndp是一个m+1行 n+1列的矩阵dp[0][0] = 0其中 第0行第i个元素表示 从一个空字符串变到word2[:i] 最少需要几步 很明显需要i步其中 第0行第j个元素表示 从一个空字符串变到word1[:i] 最少需要几步 很明显需要i步而dp[i][j] i,j均大于1 表示 从word1[:i]变到word2[:j]最少需要几步看几种情况假设我们知道从word1[:i-1]变到word2[:j]需要x步 则从word1[:i]变到wor....
设word1的长度是m
word2的长度是n
dp是一个m+1行 n+1列的矩阵
dp[0][0] = 0
其中 第0行第i个元素表示 从一个空字符串变到word2[:i] 最少需要几步 很明显需要i步
其中 第0行第j个元素表示 从一个空字符串变到word1[:i] 最少需要几步 很明显需要i步
而dp[i][j] i,j均大于1 表示 从word1[:i]变到word2[:j]最少需要几步
看几种情况
假设我们知道从word1[:i-1]变到word2[:j]需要x步 则从word1[:i]变到word2[:j]需要
x(word1[:i-1]先变到word2[:j]) + 1 (再填上一个word1[i])
假设我们知道从word1[:i]变到word2[:j-1]需要y步 则从word1[:i]变到word2[:j]需要
y + 1步 同理
假设我们知道从word1[:i-1]变到word2[:j-1]需要z步 则从word1[:i]变到word2[:j]需要
这时需要讨论一下
如果word1[i] == word[j]则我们只需要调整word1[:i-1]变到word2[:j-1]即可 不需要管最后的相等那位 此时是z步
若不相等 需要替换一次 z+1步
因此 在word1[i] == word[j]的情况下 需要min(z,x+1,y+1)
若不相等 则为min(z+1,x+1,y+1)
返回dp[-1][-1]
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
#word1,word2 = word2,word1
m = len(word1)
n = len(word2)
dp = []#m行 n列
if m == 0 and n == 0:
return 0
elif m == 0:
return n
elif n == 0:
return m
for i in range(m+1):
dp.append([0 for _ in range(n+1)])
for i in range(n+1):#先填充第0行
dp[0][i] = i
for i in range(1,m+1):
dp[i][0] = i
for x in range(1,m+1):
for y in range(1,n+1):
if word1[x-1] == word2[y-1]:
dp[x][y] = min(dp[x-1][y] +1,dp[x][y-1] + 1,dp[x-1][y-1])
else:
dp[x][y] = min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1]) + 1
return dp[-1][-1]
本文地址:https://blog.csdn.net/weixin_41545780/article/details/107578426