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

s1 = input()
s2 = input()
global l
l = list()
for i in range(1001):
    l.append([])
    for j in range(1001):
        l[i].append(0)


def f(s1: str, s2: str, i: int, j: int):

    if i == 0 or j == 0:
        a = i + j
        return a
    if l[i][j] != 0:
        return l[i][j]
    elif s1[i-1] == s2[j-1]:
        a = f(s1, s2, i - 1, j - 1)
    else:
        a = min(
            1 + f(s1, s2, i - 1, j),
            min(1 + f(s1, s2, i, j - 1), 1 + f(s1, s2, i - 1, j - 1)),
        )
        l[i][j] = a
    return a


a = f(s1, s2, len(s1) , len(s2) )
print(a)