The problem
Find the fewest edits to turn one word into another, where an edit is inserting, deleting or replacing one letter.
Input: "horse" → "ros" Output: 3 (horse → rorse → rose → ros)
Picture it
Picture fixing a typo. The table cell (i, j) holds the fewest edits to turn the first i letters of the typed word into the first j letters of the correct word. If the letters match, no edit is needed: copy the diagonal. Otherwise take 1 + the smallest of: replace (diagonal), delete (above), insert (left).
How to recognise it
- You turn one string into another with a small set of edits and want the fewest edits.
- Each edit affects one position, and what is left to fix is again a pair of shorter prefixes or suffixes.
- At the last letters there are only a few choices: match, replace, delete or insert.
- Lengths up to 500 make trying all edit sequences impossible.
- The answer is a count of edits, not the edits themselves.
Start with brute force
Compare the first letters. If they match, move on. Otherwise try the three edits and take the cheapest.
def edit_brute(a, b):
if not a:
return len(b) # type everything that is left
if not b:
return len(a) # delete everything that is left
if a[0] == b[0]:
return edit_brute(a[1:], b[1:])
return 1 + min(edit_brute(a[1:], b), # delete from a
edit_brute(a, b[1:]), # insert into a
edit_brute(a[1:], b[1:])) # replace
Each mismatch spawns three calls. For two 10-letter words with no letters in common this makes about 12 million calls, and every extra letter in both words multiplies the count by about 5 or 6. Time is exponential, space is O(m + n) for the recursion.
From brute force to the idea
- Find the waste. The calls only ever look at a pair (suffix of
a, suffix ofb), and there are just (m + 1)(n + 1) such pairs. The recursion visits the same pair many times. - Define the table.
d[i][j]is the fewest edits to turn the first i letters ofainto the first j letters ofb. - Base cases.
d[i][0] = i(delete all i letters) andd[0][j] = j(type all j letters). - Matching last letters cost nothing. If
a[i-1] == b[j-1], copy the diagonal:d[i-1][j-1]. - Otherwise pick the cheapest edit and add 1: the cell above (delete a letter of
a), the cell on the left (insert a letter ofb) or the diagonal (replace). - Read the answer. The bottom-right cell is the distance between the whole words.
This is the key idea: the best fix for two prefixes is built from the best fixes of three smaller prefix pairs.
The key idea
Classic edit distance DP. O(m × n).
Python solution
def min_distance(a, b):
d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(len(a) + 1): d[i][0] = i # delete everything
for j in range(len(b) + 1): d[0][j] = j # type everything
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] # letters already agree
else:
d[i][j] = 1 + min(d[i - 1][j], # delete
d[i][j - 1], # insert
d[i - 1][j - 1]) # replace
return d[len(a)][len(b)]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | Exponential: three branches per mismatch, no sharing | O(m + n): recursion depth |
| DP table (shown code) | O(m · n): one constant-time step per cell | O(m · n): the table; two rows would give O(n) |
For two 500-letter words that is about 250,000 cells.
Edge cases
- One word empty: the distance is the other word's length (
"" → "abc"is 3,"abc" → ""is 3). - Both empty: 0.
- Identical words: 0.
- One replace (
"a" → "b","abc" → "abd"): 1. - Reversed letters (
"abc" → "cba"): 2, two replaces, not 3. - Symmetry: swapping the words gives the same answer, because insert and delete cost the same.
- Long words: the shown code builds the full table. For 500 × 500 that is quick; there is no recursion, so no depth limit.
Common mistakes
- Leaving out the base row and column, so
"abc"against""returns 0 instead of 3. - Forgetting the replace option, which gives 4 instead of 3 for
"horse"→"ros". - Adding 1 even when the letters match, which turns identical words into a distance of their length.
- Mixing up which neighbour is insert and which is delete. The result is the same here, but the explanation will be wrong.
Now replacing a letter is not allowed: only insert and delete count, one each. For "sea" and "eat" the answer is 2. Describe your approach, then write it if you like.
Compare with our answer
Keep the table but remove the replace option from the minimum. A mismatch can then only be fixed by deleting or inserting.
def insert_delete_distance(a, b):
d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(len(a) + 1): d[i][0] = i
for j in range(len(b) + 1): d[0][j] = j
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])
return d[len(a)][len(b)]
It gives 2 for ("sea", "eat"), 4 for ("horse", "ros") and 0 for equal words. The answer also equals m + n − 2 × (longest common subsequence). Time and space O(m · n).
A strong answer mentions: dropping the diagonal from the minimum, the same base cases, and the link to the longest common subsequence.
1. You need the minimum number of single-letter changes (insert, delete or replace) to turn one word into another. Which approach fits best?
A single insert or delete shifts every later letter, so a position-by-position comparison fails. The table tries all three edits for every prefix pair and keeps the best.
2. Why does the shown code take O(m · n) time while the recursive version is exponential?
There are only (m + 1)(n + 1) prefix pairs. The recursion repeats them over and over, while the table fills each cell once from three stored neighbours.
3. The d[i - 1][j - 1] replace option is removed from the min, leaving 1 + min(d[i - 1][j], d[i][j - 1]). What does min_distance("horse", "ros") return?
Without replace, fixing a wrong letter costs two edits. Running the variant gives 4 for horse to ros, where the correct code gives 3.
Score 60% or more and the lesson is marked complete.