题解 | #计算字符串的编辑距离#
计算字符串的编辑距离
https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314?tpId=37&tqId=21275&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fdifficulty%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D37%26type%3D37&difficulty=3&judgeStatus=undefined&tags=&title=
while True:
try:
a = input()
b = input()
n, m = len(a) + 1, len(b) + 1
dp = [[0] * m for _ in range(n)]
# 初始化
for i in range(n):
dp[i][0] = i
for j in range(m):
dp[0][j] = j
for i in range(1, n, 1):
for j in range(1, m, 1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
print(dp[n-1][m-1])
except:
break
