Edit Distance
Find the minimum number of inserts, deletes and replaces to turn one word into another with a 2D DP table, and rebuild the edits from it.
Problem Understanding
Edit Distance: given two words word1 and word2, return the minimum number of operations to convert word1 into word2. Each operation inserts a letter, deletes a letter, or replaces a letter.
Example: word1 = "horse", word2 = "ros" returns 3: replace h → r, delete r, delete e.
The Intuition: Decide the Last Letter
Compare the last letters of the prefixes word1[..i] and word2[..j]:
- They match: no edit needed; the cost is that of the shorter prefixes, the diagonal
dp[i − 1][j − 1]. - They differ: one edit fixes the end, then solve a smaller problem. Replace the letter (diagonal), delete it from word1 (up), or insert word2's letter (left). Pay 1 plus the cheapest.
Turning a prefix into an empty string takes i deletes and building one from nothing takes j inserts, which fills the edges. It is the same table as Longest Common Subsequence with costs instead of matches, a core 2D dynamic programming pattern. Interleaving String uses the same grid with true/false cells.
Interactive Walkthrough
word2 runs across the top and word1 down the side, each starting with an empty prefix ∅. Each cell takes its value from the diagonal (match or replace), from above (delete) or from the left (insert). At the end, one optimal path turns green and its edits are listed in order.
Dry Run Table
Input: word1 = "horse", word2 = "ros"
| ∅ | 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 |
Answer: 3 (replace h → r, delete r, delete e).
The Solution Template
The full table with its edges set. The C version keeps it in one heap block.
Edit Distance Code
1var minDistance = function(word1, word2) {2 const m = word1.length, n = word2.length;3 const dp = Array.from({ length: m + 1 }, (_, i) => Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)));4 for (let i = 1; i <= m; i++) {5 for (let j = 1; j <= n; j++) {6 if (word1[i - 1] === word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];7 else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);8 }9 }10 return dp[m][n];11};
Edge Cases & Common Mistakes
- An empty word: the distance is the other word's length; the edges handle it.
- Forgetting the edges: leaving row 0 and column 0 as 0 makes inserts and deletes free.
- Charging for a match: a match copies the diagonal with no
+ 1. - Mixing up the directions: up is delete (from word1), left is insert (from word2), diagonal is replace.
- Space: each row only reads the previous row, so two rows of length n + 1 are enough for the distance alone.
Summary
dp[i][j] is the fewest edits turning word1's first i letters into word2's first j. Edges are i deletes and j inserts. A match copies the diagonal; otherwise pay 1 plus the cheapest of replace (diagonal), delete (up) and insert (left). The answer is dp[m][n]. O(m · n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet