Edit Distance & Typo Tolerance
In short: edit distance (Levenshtein distance) is the fewest single-character inserts, deletes and replacements that turn one string into another. It fills the same shape of table as LCS, but each cell now has three possible parents instead of two: delete (from above), insert (from the left), and keep-or-replace (the diagonal). On a match the diagonal is free; on a mismatch every option costs one more than its parent, and the cell takes the cheapest.
Someone types shrad into Quarry's search box. There is no field called
shrad, but there is one called shard, and a good engine says did you mean
shard? instead of returning nothing. To make that call, Quarry needs a number
for how far apart two strings are. The standard answer is the edit
distance (also called Levenshtein distance): the fewest single-character
inserts, deletes and replacements that turn one string into the
other.
It's the LCS table from the last lesson with one more choice per cell. That extra choice changes what the table can tell you, and what it costs to throw the table away.
Three ways to finish
Define one cell:
d[i][j]= the fewest edits that turn the firsticharacters ofainto the firstjcharacters ofb.
Think about the last step of the cheapest edit sequence:
- Keep. If
a[i-1] == b[j-1], the last characters already agree, and nothing needs to change:d[i-1][j-1]. - Replace
a[i-1]withb[j-1]:d[i-1][j-1] + 1. - Delete
a[i-1], then solve the rest:d[i-1][j] + 1. - Insert
b[j-1]at the end:d[i][j-1] + 1.
On a mismatch, take the smallest of the last three. The edges aren't zeros any
more. Turning i characters into nothing takes i deletes, so column 0 is
0, 1, 2, …, and building j characters from nothing takes j inserts, so
row 0 is too.
Filling (m + 1) × (n + 1) cells at constant work each is O(m · n) time, and
the full table costs O(m · n) space to store.
Here's the table for SORT into STORE. Each cell compares its three
neighbours, and the arrow shows which one it took:
Up is a delete, left is an insert and the diagonal is a keep or a replace. Every cell picks the cheapest of the three.
Row 0 builds STORE's prefixes from nothing, one insert per letter. Column 0 deletes SORT's prefixes, one delete per letter. 5 by 6 table. At row 0, column 5 — value 5. 10 of 30 cells filled.
def edit_distance(a, b):
d = [[max(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]
print(edit_distance("index", "indent"))Replace is what LCS was missing
If only inserts and deletes are allowed, a changed character costs 2, one delete
and one insert. That version is exactly the LCS in disguise: every character not
in the common subsequence is deleted from a or inserted from b, so the
distance is len(a) + len(b) − 2 · LCS. Replacement lets one edit do the work of
two:
a, b = "cat", "cut"
lcs = 2 # c, t
indel = len(a) + len(b) - 2 * lcs
lev = 1 # replace a with u
print(lev, indel)Two rows are enough, for the number
Each row reads only the row above and the cell to its left. Keep two rows,
prev and row, and the memory falls from O(m · n) to O(n):
Watch what that does to the picture. The same fill, in two rows:
With two rolling rows the distance is still right, but every older row is overwritten. The arrows had nowhere to live, so the edit sequence can't be recovered.
prev starts as row 0 of the full table: 0 to 5 inserts. 2 by 6 table. At row 0, column 0 — value 0. 6 of 12 cells filled.
That's the whole trade. Suggesting a spelling needs only the number, so two rows are fine. Showing the user what changed needs the path, and the path needs the rows. Lesson 4 shows how to get the path back in linear space anyway.
The two-row version has one easy mistake to make. Column 0 of every row is not 0:
SHARD becomes HARD by deleting S, so the answer is 1, but this prints 0. Fix how each new row starts.
❓ Cross-question: "Is it a knapsack?" It has the same shape: every cell is a choice between options, each built on a smaller answer, and you keep the best one. Knapsack chooses take or skip under a budget. You built that in section 6 as the best-playlist packer, and it returns in Planning DP. Edit distance chooses between keep, replace, delete and insert. Recognising "a choice per cell, the best of smaller answers" is how you spot a DP.
Your own fill, drawn
Change the two words and run it. Each cell says which edit it chose:
Your own table. The first row and column are the words, and every cell shows the cheapest way to finish.
How big can the table get?
Two documents of n characters each: the full table has (n + 1)² cells, and two rows have 2(n + 1).
| n | full table | two rows |
|---|---|---|
| 1,000 | 1,002,001 | 2,002 |
| 10,000 | 100,020,001 | 20,002 |
| 20,000 | 400,040,001 | 40,002 |
At 10,000 characters, which is a few pages of text, the full table has about 100 million cells, several hundred megabytes in Python. The distance is cheap to compute; the full table is what's expensive.
Idioms & real-world patterns
Early exit with a limit
Quarry only suggests a word within limit edits. If every cell in a row is
already above limit, no later row can come back down, because distances never
decrease along a path. So you can stop early. The main task doesn't require it,
but it's the first optimisation a real engine adds.
One edit apart, in linear time
"Are these two strings at most one edit apart?" doesn't need a table at all. Walk both with two pointers until the first mismatch, spend your one edit there, and check that the rest matches. That's the build exercise below, and a classic interview question.
⚡ Advanced: other price lists
Nothing forces every edit to cost 1. A keyboard-aware checker makes replacing a
key with its neighbour cheap. A DNA aligner charges gaps differently from
mismatches. Change the + 1s to prices and the same table works, which is the
boss exercise. Adding "swap two neighbouring letters" as a fourth move, as in
typing shrad for shard, is the capstone.
Quick practice
def edit_distance(a, b):
m, n = len(a), len(b)
d = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
d[i][0] = i
for j in range(n + 1):
d[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 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[m][n]
print(edit_distance("kitten", "sitting"))Turning an empty string into "abc" takes 3 inserts, but this prints 0. Fix the missing edge initialisation.
🎯 Your turn
Write suggest(term, vocabulary, limit). Return the word in vocabulary with
the smallest edit distance to term, as long as that distance is at most
limit. If two words tie, the one that appears first in vocabulary wins.
If no word is close enough, return None.
suggest("serch", ["search", "select", "set"], 2)→"search"suggest("shrad", ["shard", "share", "shared"], 2)→"shard"(2 edits;sharedis also 2, but comes later)suggest("xyz", ["shard"], 2)→None
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green means this piece of the app is built. ✅