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

A = input()
B = input()
m = len(A)
n = len(B)
dp = [[1 for j in range(n + 1)] for i in range(m + 1)]
for i in range(m + 1):  # 第0列
    dp[i][0] = i
for j in range(n + 1):  # 第0行
    dp[0][j] = j

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if A[i - 1] == B[j - 1]:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1)
print(dp[m][n])