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

s=input()
t=input()
def Levenshtein_Distance(s1, s2):
    len_s1 = len(s1)
    len_s2 = len(s2)

    dp = [[0 for _ in range(len_s2+1)] for _ in range(len_s1 + 1)]
    for i in range(len_s1 + 1):
        for j in range(len_s2 + 1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

    return dp[len_s1][len_s2]

print(Levenshtein_Distance(s, t))