Edit Distance: The 2D DP Grid That Measures String Difference
The 2D dynamic programming solution to Edit Distance, explained step by step — the insert/delete/replace recurrence, a worked walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Edit Distance is the problem that finally makes 2D dynamic programming click. The prompt sounds like a puzzle — how few edits turn one word into another? — but the moment you draw the grid, every hard DP problem after it (Longest Common Subsequence, Regex Matching, Distinct Subsequences) starts to look like the same machine with different rules.
It's also the algorithm behind spell-checkers, diff tools, and DNA sequence alignment. The technical name is Levenshtein distance, and once you can fill the table by hand you understand why git diff and autocorrect feel like magic.
The trick is refusing to solve the whole string at once. You solve every prefix pair — and the answer to the full problem is just the last cell you fill.
The problem
Given two strings word1 and word2, return the minimum number of operations to convert word1 into word2. You're allowed three operations, each costing 1:
- Insert a character
- Delete a character
- Replace a character
Input: word1 = "horse", word2 = "ros"
Output: 3
// horse → rorse (replace 'h' with 'r')
// rorse → rose (delete 'r')
// rose → ros (delete 'e')The operations are symmetric — an insert into word1 is the same as a delete from word2 — which is why we can treat both strings as equal partners rather than editing one destructively.
The brute force baseline
The recursive definition writes itself. Compare the last characters. If they match, they cost nothing and you recurse on both shorter strings. If they don't, you try all three edits and take the cheapest.
function minDistance(word1, word2) {
function solve(i, j) {
if (i === 0) return j; // insert all remaining of word2
if (j === 0) return i; // delete all remaining of word1
if (word1[i - 1] === word2[j - 1]) {
return solve(i - 1, j - 1); // free, skip both
}
return 1 + Math.min(
solve(i, j - 1), // insert
solve(i - 1, j), // delete
solve(i - 1, j - 1), // replace
);
}
return solve(word1.length, word2.length);
}This is correct but exponential. Every mismatch branches into three recursive calls, so the work grows like O(3^(m+n)). Worse, it recomputes the same (i, j) pair thousands of times — solve(2, 1) gets re-derived down countless different edit paths. That repeated subproblem is the exact signal that dynamic programming applies.
The key insight: prefixes, not whole strings
Define dp[i][j] as the minimum edits to turn the first i characters of word1 into the first j characters of word2. That single reframe converts recursion into a grid you fill left-to-right, top-to-bottom.
Two base cases anchor it:
dp[i][0] = i— turningicharacters into an empty string costsideletions.dp[0][j] = j— buildingjcharacters from nothing costsjinsertions.
For every interior cell, look at the current pair of characters word1[i-1] and word2[j-1]:
if they match: dp[i][j] = dp[i-1][j-1] (diagonal, free)
otherwise: dp[i][j] = 1 + min(
dp[i][j-1], // insert (left)
dp[i-1][j], // delete (top)
dp[i-1][j-1] // replace (diagonal)
)Each cell reads only three already-computed neighbors — left, top, and top-left. Match means take the diagonal untouched. Mismatch means spend one operation on top of the cheapest neighbor. That's the entire algorithm.
The optimal solution
function minDistance(word1, word2) {
const m = word1.length;
const n = word2.length;
// dp[i][j] = min operations to convert word1[0..i] to word2[0..j]
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
// Base cases: to/from an empty string costs one edit per character
for (let i = 0; i <= m; i++) dp[i][0] = i; // delete all to reach empty
for (let j = 0; j <= n; j++) dp[0][j] = j; // insert all from empty
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
// characters match — cost carries over from the diagonal
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(
dp[i][j - 1], // insert
dp[i - 1][j], // delete
dp[i - 1][j - 1], // replace
);
}
}
}
return dp[m][n];
}The answer lives in the bottom-right cell, dp[m][n] — the one cell that represents converting all of word1 into all of word2. Note the i - 1 / j - 1 indexing: row i and column j refer to prefix lengths, so the character they compare is one position back in the zero-indexed string.
Walkthrough: word1 = "horse", word2 = "ros"
Here is the completed table. Rows are prefixes of horse, columns are prefixes of ros, and ∅ is the empty string.
| ∅ | r | o | s | |
|---|---|---|---|---|
| ∅ | 0 | 1 | 2 | 3 |
| h | 1 | 1 | 2 | 3 |
| o | 2 | 2 | 1 | 2 |
| r | 3 | 2 | 2 | 2 |
| s | 4 | 3 | 3 | 2 |
| e | 5 | 4 | 4 | 3 |
The top row and left column are the base cases. Trace a few interior cells to see the recurrence fire:
| Cell | Chars compared | Match? | Computation | Result |
|---|---|---|---|---|
| dp[1][1] | h vs r | no | 1 + min(left 1, top 1, diag 0) | 1 |
| dp[2][2] | o vs o | yes | diag dp[1][1] | 1 |
| dp[3][1] | r vs r | yes | diag dp[2][0] | 2 |
| dp[4][3] | s vs s | yes | diag dp[3][2] | 2 |
| dp[5][3] | e vs s | no | 1 + min(left 4, top 2, diag 3) | 3 |
dp[2][2] is the satisfying one: o === o, so the cost drops straight down the diagonal to 1 — no operation spent. The final cell dp[5][3] mismatches (e vs s), so it takes the cheapest neighbor (the top, dp[4][3] = 2, a delete) and adds one, landing on 3. That matches the three-edit sequence from the problem statement.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Naive recursion | O(3^(m+n)) | O(m+n) | three branches per mismatch, no memoization |
| 2D DP table | O(m·n) | O(m·n) | fill each of (m+1)(n+1) cells once, O(1) work each |
| Rolling array | O(m·n) | O(min(m,n)) | each row needs only the previous row |
The table version does constant work per cell — one comparison and one min of three values — across an m × n grid, so O(m·n) time is exact. Space is the grid itself, but since each row depends only on the row above, you can collapse it to two rows (or one, with care) for O(min(m, n)) space when memory is tight.
Common mistakes
- Off-by-one on the character index.
dp[i][j]uses prefix lengths, so you compareword1[i-1]andword2[j-1], notword1[i]. Usingi/jdirectly reads past the intended character or skips the first one. - Forgetting the base row and column. If you leave the empty-string edges as zeros instead of
dp[i][0] = ianddp[0][j] = j, every downstream cell inherits wrong costs. Initialize them before the double loop. - Adding 1 on a match. A matching pair costs nothing — copy the diagonal directly. Writing
1 + dp[i-1][j-1]on a match inflates the answer. - Picking the wrong neighbor for each op. Insert is the left cell
dp[i][j-1], delete is the top celldp[i-1][j], replace is the diagonaldp[i-1][j-1]. Swapping insert and delete still returns the right number here (they're symmetric) but breaks when you try to reconstruct the actual edit sequence.
Where this pattern shows up next
Edit Distance is the 2D form of the DP you first meet in one dimension. These build the same muscle from the ground up:
- Fibonacci Number — the simplest recurrence, where a cell depends on the two before it.
- Climbing Stairs — the same two-term recurrence dressed as a counting problem.
- Min Cost Climbing Stairs — adds a
minover predecessors, the exact choice Edit Distance makes at every mismatch. - House Robber — a
min/maxdecision per cell, the 1D cousin of picking the cheapest of three neighbors.
You can also step through Edit Distance interactively to watch the matrix fill cell by cell, with the three candidate neighbors lighting up at every mismatch.
FAQ
Why is Edit Distance a 2D DP problem?
Because the state depends on two independent positions: how far you've progressed through word1 and how far through word2. A single index can't capture that, so you need a grid indexed by both prefix lengths. Each cell dp[i][j] answers one self-contained subproblem — convert the first i characters into the first j — and the full answer is the bottom-right corner where both prefixes are complete.
What is the difference between Edit Distance and Levenshtein distance?
They're the same thing. Levenshtein distance is the formal name for the minimum number of single-character insertions, deletions, and substitutions needed to transform one string into another — each weighted equally at cost 1. LeetCode's "Edit Distance" is a direct implementation of it. Variants like Damerau-Levenshtein add a fourth operation (transposing adjacent characters), but the classic problem uses exactly the three edits shown here.
What is the time and space complexity of Edit Distance?
The 2D DP solution runs in O(m·n) time and O(m·n) space, where m and n are the two string lengths. Every cell is computed once with a constant-time comparison and a three-way minimum. Because each row only reads the row directly above it, you can reduce space to O(min(m, n)) by keeping just two rows — the time stays O(m·n).
Why does a matching character cost zero operations?
If the current characters are equal, aligning them requires no edit — the optimal cost is whatever it took to align the two prefixes before them, which is the diagonal cell dp[i-1][j-1]. Spending an operation on an already-matching pair would be wasteful, and the recurrence would never choose it because copying the diagonal is always at least as cheap as any 1 + neighbor alternative.
Can I reconstruct the actual edits, not just the count?
Yes. After filling the table, walk backward from dp[m][n] to dp[0][0]. At each cell, check which neighbor produced the value: a diagonal move on matching characters is a "keep," a diagonal on a mismatch is a "replace," a move up is a "delete," and a move left is an "insert." The reversed sequence of moves is one valid minimum-edit script. This is exactly how diff tools turn the distance number into a concrete list of changes.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.