Speed Up Edit Distance with a Cached Helper

Spell checkers suggest the word closest to what you typed by measuring edit distance. That is the fewest single-character insertions, deletions and substitutions that turn one string into another, each costing 1. The word kitten becomes sitting with two substitutions and one insertion, so the distance is 3.

The starter's recursion is right, but it puts @cache on the public function and crashes on input that is not two strings. Move the cache to a private helper, and put a checking function in front of it.

edit_distance("kitten", "sitting")  # 3
solve([["kitten", "sitting"], ["", "abc"], [123, "abc"], ["a"]])
# [3, 3, "TypeError", "TypeError"]

What to write

• A private helper, such as _distance(a: str, b: str) -> int, decorated with @cache from functools. When one string is empty, return the length of the other. When the first characters match, return the distance between the rest of the two strings. Otherwise return 1 plus the smallest of three distances, after dropping the first character of a, of b, or of both.
• edit_distance(a: object, b: object) -> int, with no decorator. If either argument is not a str, raise TypeError before calling the helper. Otherwise return the helper's result.
• solve(pairs: list[list[object]]) -> list[object]. For each inner list, in order, append the distance when the list has exactly two items and both are strings. Otherwise append the string "TypeError" and go on to the next list.

The tests check the results, not which decorator you used, but the cached helper is the point of the lesson. Keep the public function uncached, so mypy checks the calls to it.

Edge cases

• An empty outer list gives [].
• Empty strings are valid. The distance from "" to "abc" is 3, and from "" to "" is 0.
• Compare characters exactly, with no change of case. Spaces and punctuation count like any other character.
• Swapping two neighbouring characters costs two edits, not one.
• Booleans are not strings, so a pair such as [True, False] gives "TypeError".
• The hidden tests include strings longer than 40 characters. Without the cache, they take far too long.