Calculate edit distance of two strings. #DynamicProgramming

levenshtein_distance.py

def levenshtein_distance(s1: str, s2: str) -> int:
    """
    求解两个字符串的莱文斯坦距离。
    """
    len1, len2 = len(s1) + 1, len(s2) + 1
    f = list(range(len2))
    for i in range(1, len1):
        t1 = f[0]
        f[0] += 1
        for j in range(1, len2):
            t2 = f[j]
            if s1[i - 1] == s2[j - 1]:
                f[j] = t1
            else:
                f[j] = min([t1, f[j - 1], f[j]]) + 1
            t1 = t2
    return f[-1]


if __name__ == "__main__":
    print("levenshtein_distance=", levenshtein_distance(input("s1="), input("s2=")))