Edit distance

An edit is one of three changes to a string: insert a letter anywhere, delete a letter, or replace a letter with another. Return the fewest edits that turn a into b. This number is the edit distance (also called the Levenshtein distance).

edit_distance("kitten", "sitting")  # 3
# k -> s, e -> i, insert g
edit_distance("horse", "ros")       # 3
edit_distance("", "abc")            # 3

Limits

• Each string has up to 1,000 letters. Aim for O(len(a) × len(b)).
• Python stops at about 1,000 nested calls, and a function wrapped in functools.cache stops after a few hundred in the browser. The big tests need far more than that, so memoised recursion fails them. Fill a table with a loop (lesson 3).