Forgive typos with edit-distance DP
Continues from the last build: An engine that can search exact terms, autocomplete prefixes, rank results, and walk a graph of related terms, but still returns nothing for a typo like pyhton.
Type "pyhton" into it and the last rung's related-term graph shrugs, there is no edge from a misspelling to anything, because graph edges only connect terms that already exist in the vocabulary.
What you'll build
By the end it takes any typed word, computes its edit distance to every term in the vocabulary using a DP table you built and then space-optimized, and returns a ranked "did you mean" list, backed by a timed benchmark that proves the table beats naive recursion by an order of magnitude and that the two-row version holds memory flat as inputs grow.
See how we teach, before you sign up
You don't just get code dumped on you. Every starter file and every solution is explained line-by-line, in plain English. Here's one real file from this project:
from functools import wraps
CALLS = 0
def edit_distance_naive(a: str, b: str) -> int:
"""Pure recursive Levenshtein distance, no memo. Feel the blowup."""
global CALLS
def dp(i: int, j: int) -> int:
global CALLS
CALLS += 1
if i == 0:
return j # insert all of b[:j]
if j == 0:
return i # delete all of a[:i]
if a[i - 1] == b[j - 1]:
return dp(i - 1, j - 1) # chars match, no edit spent
insert = dp(i, j - 1) + 1
delete = dp(i - 1, j) + 1
substitute = dp(i - 1, j - 1) + 1
return min(insert, delete, substitute)
return dp(len(a), len(b))
if __name__ == "__main__":
CALLS = 0
print(edit_distance_naive("pyhton", "python"))
print("calls:", CALLS)
CALLS = 0
print(edit_distance_naive("algorithm", "logarithm"))
print("calls for 9-char pair:", CALLS)
Reading this file
CALLS += 1A global counter so you can literally count how many times dp(i, j) fires. Watch this number, not just the runtime clock.if a[i - 1] == b[j - 1]: return dp(i - 1, j - 1) # chars match, no edit spentThe free move: matching characters cost nothing, so you only recurse on the smaller prefix pair.insert = dp(i, j - 1) + 1 delete = dp(i - 1, j) + 1 substitute = dp(i - 1, j - 1) + 1The three edits Levenshtein allows. Each recurses into an overlapping subproblem that a memo-less call tree will recompute over and over.return min(insert, delete, substitute)The recurrence's payoff line: cheapest of the three edits, one per operation.print("calls for 9-char pair:", CALLS)Run this on a 9-letter pair and the call count already runs into the tens of thousands, that is the exponential blowup this rung exists to fix.
Naive recursive version, deliberately left unmemoized so milestone 1 can watch it blow up before fixing it.
That's 1 of 8 explained code blocks in this single project.
The build, milestone by milestone
- 1
Read the recurrence and feel the naive blowup
4 guided stepsEvery DP problem you will ever meet starts as a recurrence over overlapping subproblems. If you memorize the trick (build a table) without first watching the recursion recompute the same (i, j) pair thousands of times, the table will feel like a magic incantation instead of an obvious fix. This milestone buys you the lived pain that makes memoization click.
- 2
Memoize it into a bottom-up DP table
4 guided stepsThe table form makes the O(m*n) cost visible as literal cells you can count, rows times columns, and it is the structure the next milestone compresses. Seeing the table as a grid, not a call tree, is what makes the later two-row optimization obvious instead of mysterious.
- 3
Space-optimize the table to two rows
4 guided stepsFor a spell checker you never need the full table, only the final number, dist(a, b). Keeping the whole table alive to answer one integer wastes memory that matters once you are scoring a typo against thousands of vocabulary terms.
- 4
Rank spell-correction candidates against the vocabulary
4 guided stepsA raw distance number is not a feature, a ranked "did you mean" list is. This is the milestone where edit distance stops being an isolated algorithm exercise and becomes the thing that actually fixes the pain from the scenario: pyhton now resolves to python.
- 5
Benchmark it and prove the O(m*n) claim
4 guided stepsBig-O reasoning without a timed number on a growing input is just a claim. This rung's whole premise was escaping the naive version's exponential blowup, so closing it with an actual measurement is what makes the improvement real instead of assumed.
What's inside when you start
You'll walk away with
This is portfolio-grade. Build it free.
Sign up to unlock every milestone step-by-step, the code skeletons, full reference solutions, and checkable tasks, with your progress saved as you build.
Start building