题解 | 计算字符串的编辑距离

import sys
   
raw_input = []
for i,line in enumerate(sys.stdin):
    raw_input.append(line.strip())
    if i == 2:
        break

MAX_VAL = float('inf')
A, B = raw_input[0], raw_input[1]
row, col = len(A), len(B)
dist = [[MAX_VAL]*(col + 1) for _ in range(row + 1)]
for i in range(row + 1):
    dist[i][0] = i
for j in range(col + 1):
    dist[0][j] = j

for i in range(1, row + 1):
    for j in range(1, col + 1):
        # dist[i][j] = min([dist[i-1][j], dist[i][j-1], dist[i-1][j-1]]) + int(A[i-1] != B[j-1]) , this is wrong, we use dist[i][j] to store edit distance of strings ends with i and j.
        if A[i-1] == B[j-1]:
            dist[i][j] = dist[i-1][j-1]
        else:
            dist[i][j] = min([dist[i-1][j], dist[i][j-1], dist[i-1][j-1]]) + 1
 
# for s_row in dist:
#     print(s_row)
# print(row, col)
print(dist[-1][-1])