编辑距离

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]