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

while True:
    try:
	  	# 此题实际上就是构造一个bp表，并且按照bp表的规则来演绎，最后取得表格有下家的元素的值
        s1 = input()
        s2 = input()
        l1 = len(s1)+1
        l2 = len(s2)+1
        dis = [ [0]*l1 for _ in range(l2)] # 建造一个bp表值先填充0，注意建造list时，最外面部分不能用* 

        for i in range(l1): # 第一行填入值
            dis[0][i] = i

        for i in range(l2): # 第二行填入值
            dis[i][0] = i

        for i in range(1,l1): # 每一列
            for j in range(1,l2): # 每一行
                if s1[i-1] != s2[j-1]: # 规则1 若遍历到的字符不等，取三者最小+1
				  # 注意获取某元素按照dis[行数][列数]来提
                    dis[j][i] = min(dis[j-1][i],dis[j][i-1],dis[j-1][i-1])+1 
                else: # 规则2 若字符相等，取其表中左上邻格的数
                    dis[j][i] = dis[j-1][i-1]
        
        print(dis[l2-1][l1-1]) # 输出结果

    except:
        break