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

#思路来自高赞解答，仅练习记录用
def cal(a,b):
    array = [[x for x in range(len(a)+1)] for y in range(len(b)+1)] #创建矩阵，+1使得有0行0列
    for w in range(1, len(b)+1): #对0列赋值（0行已在上一步赋值）
        array[w][0] = array[w-1][0] + 1
    for i in range(1, len(b)+1): #遍历每行
        for j in range(1, len(a)+1): #遍历每行中的每一项
            if b[i-1] == a[j-1]: #若当前字符相同，步骤数拷贝左上角的值
                array[i][j] = array[i-1][j-1]
            else: #否则，取（左上，上，左）中最小值+1
                a1 = array[i-1][j-1]
                a2 = array[i-1][j]
                a3 = array[i][j-1]
                array[i][j] = min(a1,a2,a3)+1
    return array[-1][-1]

while True:
    try:
        x = input()
        y = input()
    except:
        break
    else:
        print(cal(x,y))