2025/10/16
思路:动态规划
设word1[1..i]到word2[1..j] 的编辑距离是 D[i][j]
D[i][j] = D[i-1][j-1] if a[i] == a[j] = min(D[i][j-1] +1, D[i-1][j] + 1, D[i-1][j-1]+1) if a[i] !=a[j] D[i][0] = i D[0][j] = j
评价:完全正确,就是想起来非常费劲
手写代码:
def minDistance(word1, word2):
m = len(word1)
n = len(word2)
D = [[] * n] * m
for i in range(m):
D[i][0] = i
for j in range(n):
D[0][j] = j
for k in range(1, m + n +1):
for i in range(1, k):
j = k - i
if a[i] == a[j]:
D[i][j] = D[i-1][j-1]
else:
D[i][j] = min(D[i][j-1] +1, D[i-1][j] + 1, D[i-1][j-1]+1)
return D[m][n]