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

while True:
    try:
        str1 = input()
        str2 = input()
        m = len(str1)
        n = len(str2)         
        dp = [[1 for i in range(n+1)] for j in range(m+1)]#重点注意二维数据的创建方法，重点注意其横竖坐标，注意注意
        for i in range(n+1):
            dp[0][i] = i
        for j in range(m+1):
            dp[j][0] = j            
        for i in range(1,m+1):
            for j in range(1,n+1):
                if str1[i-1] == str2[j-1]:#如果当前两个字母相同，则跳过，步数不增加
                    dp[i][j]=dp[i-1][j-1]
                else:  #如果两个字母不同，则有三种方式可以达成，替换、删除、添加，选择最小的前状态，步数加1
                    dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
        print(dp[m][n])
    except:
        break