Edit Distance

Compute Levenshtein distance — the fewest single-character insertions, deletions or substitutions turning one word into another. Print it for four pairs.

'kitten' -> 'sitting': 3
'flaw' -> 'lawn': 2
'abc' -> 'abc': 0
'' -> 'hello': 5

Build a (len(a)+1) x (len(b)+1) table. Each cell is 1 + the cheapest of delete/insert/substitute, or the diagonal when the characters match.

def edit_distance(a, b):
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        cur = [i]
        for j, cb in enumerate(b, 1):
            if ca == cb:
                cur.append(prev[j - 1])
            else:
                cur.append(1 + min(prev[j], cur[j - 1], prev[j - 1]))
        prev = cur
    return prev[-1]

for x, y in (("kitten", "sitting"), ("flaw", "lawn"), ("abc", "abc"), ("", "hello")):
    print(f"{x!r} -> {y!r}: {edit_distance(x, y)}")

Run your code to check it…