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

from math import inf
import sys

s = input().strip()
t = input().strip()

m, n = len(s), len(t)
dp = [[inf] * n for _ in range(m)]
for j in range(n):
    if s[0] in t[:j+1]:
        dp[0][j] = j
    else:
        dp[0][j] = j+1
for i in range(m):
    if t[0] in s[:i+1]:
        dp[i][0] = i
    else:
        dp[i][0] = i+1

for i in range(1, m):
    for j in range(1, n):
        if s[i] == t[j]:
            dp[i][j] = 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[m-1][n-1])


# s[:i+1]与t[:j+1]的编辑距离
# def dfs(i, j):
#     if i<0 and j<0:
#         return 0
#     if i<0:
#         return j+1
#     if j<0:
#         return i+1

#     if s[i] == t[j]:
#         return dfs(i-1, j-1)
#     return min([dfs(i-1, j-1) + 1, dfs(i, j-1) + 1, dfs(i-1, j)+1])
    
# s -> t
# print(dfs(len(s)-1, len(t)-1))