Step 6 of 6

Edit distance

How different are two words? The edit distance (or Levenshtein distance) is the smallest number of single-character edits that turn one into the other, where an edit is inserting a character, deleting one, or replacing one with another. kitten → sitting takes 3: replace k with s, replace e with i, insert g. Spell checkers suggest the dictionary words closest to what you typed, search engines use it for "did you mean", and DNA tools use variations of it.

The recurrence

Let D[i][j] be the edit distance between the first i characters of a and the first j characters of b.

• Turning i characters into nothing takes i deletions: D[i][0] = i. Turning nothing into j characters takes j insertions: D[0][j] = j.

• If a[i - 1] == b[j - 1], the last characters already match and cost nothing: D[i][j] = D[i - 1][j - 1].

• Otherwise, the last edit is one of three, each costing 1:

  • replace a[i - 1] with b[j - 1]: D[i - 1][j - 1] + 1
  • delete a[i - 1]: D[i - 1][j] + 1
  • insert b[j - 1] at the end: D[i][j - 1] + 1

  and D[i][j] is the smallest of the three.

Here's the full table for cat → cut:

Read it like the LCS table: D[1][1] is 0 because c matches c; D[2][2] is 1 because a ≠ u, and the cheapest option is replacing (D[1][1] + 1); D[3][3] is 1 because t matches t and costs nothing on top of D[2][2]. The answer is the bottom-right entry: one replacement.

A tiny spell checker

With edit_distance written, a suggestion is just the dictionary word with the smallest distance to the typed word. Plain edit distance counts swapping two neighboring letters (teh → the) as two replacements. The Damerau-Levenshtein variant adds a "transpose" edit to fix that; real spell checkers also weight edits by which keys sit next to each other.

Recognizing DP problems

Across this module, the problems had the same signs: a question about the best (fewest, most, longest) or how many, a choice at each step (which coin, take or skip, which edit), and sub-questions that repeat. Solving one always went the same way: define what a table entry means, write how an entry is built from smaller ones, set the base cases, and fill the table in an order where everything needed is ready.

Your turn: write edit_distance(a, b), then suggest(word, dictionary), returning the dictionary word with the smallest edit distance to word (the earliest one in the list on a tie). The dictionary is never empty.

Previous: The 0/1 knapsack