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

s1 = input()
s2 = input()
n1 = len(s1)
n2 = len(s2)

dp = [[0 for _ in range(n2 + 1)] for _ in range(n1 + 1) ]
# print(dp)

for i in range(n1+1):
    dp[i][0] = i
for j in range(n2+1):
    dp[0][j] = j 
# print(dp)

for i in range(1,n1+1):
    for j in range(1,n2+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = min(dp[i-1][j-1],dp[i][j-1]+1,dp[i-1][j]+1)
        else:
            dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1

print(dp[n1][n2])