DP: Edit Distance
Hard+100 XPFewest insert/delete/replace edits to turn one word into another — the classic 2D string DP.
No visualization loaded.
Watch
—
Press Run to begin.
How many single-letter edits does it take to turn one word into another? You're allowed three moves: insert a letter, delete a letter, or replace one letter with another. Spell-checkers and DNA comparison use this. We build a table where dp[i][j] = the fewest edits to turn the first i letters of word A into the first j letters of word B. Two cases: if the current letters MATCH, you pay nothing and copy the diagonal cell. If they DIFFER, you take 1 + the cheapest of three neighbors — replace (diagonal), delete (up), or insert (left).
▸Why do the three neighbor cells mean insert, delete, and replace?
Look at the last move that lands you in dp[i][j]. REPLACE turns A's i-th letter into B's j-th, so both shrink by one → come from the diagonal dp[i-1][j-1]. DELETE drops A's i-th letter, so only A shrinks → come from up, dp[i-1][j]. INSERT adds B's j-th letter into A, so only B is 'consumed' → come from the left, dp[i][j-1]. Each move costs 1, so it's 1 + the cheapest of those three.
▸Why is a match free (just copy the diagonal)?
If A's i-th letter already equals B's j-th letter, you don't need to edit it — it's already correct. So the cost of aligning the first i and j letters is exactly the cost of aligning the first i-1 and j-1 (the diagonal), with zero added. Matching letters are the cheap path the table loves to follow.
▸Why does row 0 count up 0,1,2,3… and column 0 too?
Row 0 means word A is empty; to build the first j letters of B from nothing you must INSERT j letters → cost j. Column 0 means B is empty; to reduce the first i letters of A to nothing you DELETE i letters → cost i. Those edges are the honest base cases everything else stacks on.
▸How is this like Knapsack?
Both fill a 2D table where each cell is the best of a few already-solved neighbors. Knapsack chose between 'skip' and 'take' (a max of two cells); Edit Distance chooses between insert/delete/replace (a min of three) or a free diagonal copy on a match. Same 2D-table machinery, different local choice.
How the work grows
O(m × n) is slow — explodes on big inputs. One cell per pair of prefixes: m×n cells, each O(1) from three neighbors. Trying every sequence of edits by brute force is exponential — the table reuses overlapping prefix alignments. Memory is the full table, though only the previous row is truly needed.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.