题解 | #计算字符串的编辑距离#
计算字符串的编辑距离
http://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314
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])