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

# str1 = STR1
# str2 = STR2
# 二维数组dp[m][n]存储两个字符串的编辑距离值，m, n分别为：m = len(str1) + 1 和 n = len(str2) + 1
# dp[i][j]表示字符串str1的前i个字符与字符串str2的前j个字符的编辑距离
# dp[i][j]是如下四种情况下的最小值：
# (1) dp[i][j] = dp[i-1][j-1]。此时知道str1的前i-1个字符到str2的前j-1个字符的编辑距离，且str1[i] = str2[j]，此时不增加距离
# (2) dp[i][j] = dp[i-1][j-1] + 1。此时知道str1的前i-1个字符到str2的前j-1个字符的编辑距离，且str1[i] != str2[j]，需要修改str1[i]或str2[j],此时距离+1
# (3) dp[i][j] = dp[i-1][j] + 1。此时知道str1的前i-1个字符到str2的前j个字符的编辑距离，那么str1的前i个字符到str2的前j个字符的距离就要加上str1的第i个字符，即+1
# (4) dp[i][j] = dp[i][j-1] + 1。此时知道str1的前i个字符到str2的前j-1个字符的编辑距离，那么str1的前i个字符到str2的前j个字符的距离就要加上str2的第j个字符，即+1
# dp的第1行和第1列需要赋予初始值，表示空字符串到str1和str2的距离
def test(str1, str2):
    m = len(str1) + 1
    n = len(str2) + 1
    dp = [[1] * m for i in range(n)]
    for i in range(0, m):
        dp[0][i] = i
    for j in range(0, n):
        dp[j][0] = j
    for i in range(1, n):
        for j in range(1, m):
            if str1[j - 1] == str2[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                x = dp[i - 1][j - 1] + 1
                y = dp[i - 1][j] + 1
                z = dp[i][j - 1] + 1
                dp[i][j] = min(x, y, z)
    return dp[n-1][m-1]
while True:
    try:
        str1 = input()
        str2 = input()
        re = test(str1, str2)
        print(re)
    except:
        break