levenshtein.py

def levenshtein_distance(s1: str, s2: str) -> int:
    if s1 == s2:
        return 0

    if not s1:
        return len(s2)
    if not s2:
        return len(s1)

    prev, curr = None, range(len(s2) + 1)
    for i in range(len(s1)):
        prev, curr = curr, [i + 1] + [0] * len(s2)
        for j in range(len(s2)):
            curr[j + 1] = min(
                prev[j + 1] + 1,             # Deletion
                curr[j] + 1,                 # Insertion
                prev[j] + (s1[i] != s2[j]),  # Substitution
            )

    return curr[-1]