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

import sys

line1=line2=None
for i, line in enumerate(sys.stdin):
    line=line.strip()
    if i%2==0:
        line1=line
    else:
        line2=line
    
        len1, len2=len(line1)+1, len(line2)+1
        edit=[[i+j for j in range(len2)] for i in range(len1)]

        for i in range(1, len1):
            for j in range(1, len2):
                if line1[i-1]==line2[j-1]:
                    edit[i][j]=edit[i-1][j-1]
                else:
                    edit[i][j]=min(edit[i-1][j-1], edit[i-1][j], edit[i][j-1])+1
        print(edit[len1-1][len2-1])