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

python 动态规划，思路写的清楚，不知道有没有问题

while True:
    try:
        str1 = input().strip()   # 第一个字符串
        str2 = input().strip()   # 第二个字符串
        # 构建dp数组，行为第一个字符串，列为第二个字符串
        # dp[i][j]为第一个字符串前i个字符与第二个字符串前j个字符的最小编辑距离
        # 同时初始化第一行，即第一个字符串与空字符串的编辑距离，dp[0][j] = j
        dp = [[i for i in range(len(str1)+1)] for j in range(len(str2)+1)]
        # 初始化第一列，即第二个字符串与空字符串的编辑距离，dp[i][0] = i
        for i in range(len(str2)+1):
            dp[i][0] = i
        # 这题首列首行都初始化了，遍历顺序可以颠倒
        for i in range(1, len(str1)+1):
            for j in range(1, len(str2)+1):
                # 如果新加的字符相等，则编辑距离不变
                if str1[i-1] == str2[j-1]:
                    dp[j][i] = dp[j-1][i-1]
                # 如果新加字符不相等，则新增加的编辑距离等于‘加’、‘减’、‘插入’三种操作的中距离最小值
                # 长度分别为 i-1 和 j 的字符串的编辑距离已知，那么加1即可；(str1[0:i-1]加str2[j])
                # 长度分别为 i 和 j-1 的字符串的编辑距离已知，那么加1即可；（str2[0:j]减str2[j]）
                # 长度分别为 i-1 和 j-1 的字符串的编辑距离已知，那么加1即可；（str1[i-1]和str2[i]之间插入str2[j]）
                else:
                    add = dp[j-1][i] + 1    # 加
                    sub = dp[j][i-1] + 1    # 减
                    ins = dp[j-1][i-1] + 1  # 插入
                    dp[j][i] = min(add, sub, ins)
        print(dp[-1][-1])
    except:
        break