Practice: Edit Distance
How spell checkers think.
When you type kitten, but meant sitting, how far off were you? Edit distance counts the fewest single letter changes needed. Insert a letter, delete a letter, or swap one letter for another. Spell checkers use it to suggest corrections.

- kitten → sitting
- Fewest single letter edits
- Insert, delete, or replace
A grid of edits
Like the common subsequence, we fill a grid. The first row and column count edits from an empty word. If two letters match, no edit is needed, so we copy the diagonal. Otherwise, it's one, plus the cheapest of delete, insert, or replace. Run it. Kitten to sitting takes three edits.
def edit_distance(a, b):
d = [[i + j if i * j == 0 else 0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
d[i][j] = d[i - 1][j - 1]
else:
d[i][j] = 1 + min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1])
return d[-1][-1]
for a, b in [("kitten", "sitting"), ("flaw", "lawn"), ("same", "same")]:
print(a, "->", b, edit_distance(a, b))kitten -> sitting 3 flaw -> lawn 2 same -> same 0
Suggesting corrections
A spell checker compares the word you typed with real words, and suggests the ones with the smallest edit distance. Kitten to sitting is three. Replace K with S, replace E with I, and add a G. The same algorithm compares DNA, and powers fuzzy search.
| key | value |
|---|---|
| Delete | cell above + 1 |
| Insert | cell left + 1 |
| Replace | diagonal + 1 |
| Match | diagonal, free |
Summary
Edit distance fills a grid, choosing the cheapest of insert, delete, or replace. That's the end of dynamic programming. Next, backtracking, for exploring every possibility.
Key takeaways- Grid of prefixes
- Match is free
- 1 + cheapest edit