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

def editdistance(s1, s2):
    topen = [(s1, s2, 0)]
    opened = set()
    while True:
        w1, w2, value = topen.pop(0)
        if (w1, w2) in opened:
            continue
        if w1 == w2:
            return value
        opened.add((w1, w2))
        while w1 and w2 and w1[0] == w2[0]:
            w1, w2 = w1[1:], w2[1:]
        value += 1
        topen += [(w1,w2[1:],value),
                  (w1[1:],w2,value),
                  (w1[1:],w2[1:],value)]
a = input()
b = input()
print(editdistance(a,b))