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

# 参考https://www.bilibili.com/video/BV1na4y1E771/?spm_id_from=333.337.search-card.all.click&vd_source=a78f1e93369e62f172303afd6e198da8


s1 =input()
s2 = input()
m = len(s1)
n = len(s2)

dp = [[None for j in range(n+1)] for i in range(m+1)]

def f(s1,s2):
    for i in range(m+1):
        dp[i][0]=i
    for j in range(n+1):
        dp[0][j]=j

    for i in range(1,m+1):
        for j in range(1,n+1):
            if s1[i-1]==s2[j-1]:
                dp[i][j]=dp[i-1][j-1]
            else:
                dp[i][j]=min(dp[i-1][j-1]+1,dp[i][j-1]+1,dp[i-1][j]+1)
    return dp[i][j]
print(f(s1,s2))