Edit Distance
Dynamic Programming: lesson 8 of 10
Insert, delete, or replace — count the cheapest route.
Lesson 8 of 10 · 6 min
Edit Distance
Step 1 of 20
Turn flaw into lawn. One row per prefix of the first word, one column per prefix of the second.
The Idea
Turn one string into another with inserts, deletes, and replacements, counting the cheapest sequence. Every grid cell asks what the three slightly shorter problems cost. Matching characters are free and copy the diagonal; a mismatch pays one on top of whichever of the three neighbours is cheapest. Only the previous row is ever needed.
Real-World Example
The "did you mean" line under a mistyped search. The engine scores your typo against dictionary words by how many single-character fixes separate them, so a word one edit away is offered before one that is three edits away.
The Code
def edit(a, b):
row = list(range(len(b) + 1)) # cost of building b's prefixes from ""
for i in range(1, len(a) + 1):
new = [i] + [0] * len(b)
for j in range(1, len(b) + 1):
cost = 0 if a[i - 1] == b[j - 1] else 1
new[j] = min(row[j] + 1, # delete
new[j - 1] + 1, # insert
row[j - 1] + cost) # match or replace
row = new
return row[len(b)]
print(edit("kitten", "sitting")) # 3
print(edit("flaw", "lawn")) # 2Your turn
Put the steps in the right order.
- Fill each remaining cell with the cheapest of delete, insert, and replace
- Read the bottom-right cell as the distance
- Fill row 0 and column 0 with 0, 1, 2, ... — the cost against an empty string
- Lay out a grid with one row per prefix of a and one column per prefix of b
Mini quiz
1 / 3