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

while True:
    try:
        x = input()
        y = input()
        lx, ly = len(x), len(y)

        a = [[0] * (ly+1) for _ in range(lx+1)]
        # a[i][j] 表示 长度为i的x 和长度为j的 y所匹配的最小距离
        # 求 a[lx][ly]

        # a[0][j] = j  a[i][0] = 0
        for j in range(ly+1):
            a[0][j] = j
        for i in range(lx+1):
            a[i][0] = i


        # 动态规划 考虑当最后一个字母相同时 a[i][j] = a[i-1][j-1]+0
        # x[i] != y[j] 时
        # 替换 =a[i-1][j-1]+1  最后插入a[i-1][j]+1  删除a[i][j-1]+1 求最小值

        for i in range(lx):
            for j in range(ly):
                if x[i] == y[j]:
                    # x[0] 对应长度为 1 的 lx
                    a[i+1][j+1] = a[i][j]+0
                else:
                    res = [a[i][j]+1, a[i][j+1]+1, a[i+1][j]+1]
                    a[i+1][j+1] = min(res)

        print(a[lx][ly])
    except:
        break