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

str1=input()
str2=input()
n1=len(str1)+1
n2=len(str2)+1
dp=[[0]*n2 for i in range(n1)]

for i in range(n1):
    dp[i][0]=i
for j in range(n2):
    dp[0][j]=j
for i in range(1,n1):
    for j in range(1,n2):
        if(str1[i-1]==str2[j-1]):
            dp[i][j]=dp[i-1][j-1]
        if(str1[i-1]!=str2[j-1]):
            dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1
print(dp[-1][-1])