Given two strings word1 and word2, return the minimum number of single-character operations needed to transform word1 into word2.
The permitted operations are: insert a character, delete a character, and replace a character.
Example
horse → rorse (replace h), → rose (delete r), → ros (delete e).
Constraints
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters.
Intuition
A first pass tries every possible way of turning word1 into word2 directly: at each pair of prefix lengths (i, j), if the last characters already match, keep going for free; otherwise try all three allowed operations — replace, delete, insert — recursing into whichever leftover subproblem each one creates, and keep whichever choice ends up cheapest.
function minDistance(word1, word2) {
// solve(i, j) = edit distance between the first i characters of word1
// and the first j characters of word2.
function solve(i, j) {
// No characters left in word1: insert the remaining j characters of word2.
if (i === 0) return j;
// No characters left in word2: delete the remaining i characters of word1.
if (j === 0) return i;
if (word1[i - 1] === word2[j - 1]) {
// Last characters already match — no operation needed here.
return solve(i - 1, j - 1);
}
// No match: try all three operations and keep the cheapest.
const replace = solve(i - 1, j - 1);
const deleteChar = solve(i - 1, j);
const insertChar = solve(i, j - 1);
return 1 + Math.min(replace, deleteChar, insertChar);
}
return solve(word1.length, word2.length);
}This is O(3^(m+n)) roughly — exponential, because solve(i, j) gets re-derived from scratch every time a different sequence of replace/delete/insert choices happens to land on the same (i, j) pair, and there are only (m + 1) × (n + 1) distinct pairs total. Can we do better?
The key observation: solve(i, j) always means the same thing — the edit distance between the first i characters of word1 and the first j characters of word2 — so once it's answered it never needs answering again. That's the overlapping-subproblems signature dynamic programming exists to eliminate.
It's the same signature Longest Common Subsequence uses for its own two-string alignment table, but the recurrence itself is different. LCS only ever skips a character from one string or the other when they mismatch — a two-way branch, taking the max — and a match costs nothing extra either way. Edit distance additionally allows replacing a character — a three-way branch (delete, insert, replace), taking the min — and while a match still costs nothing, a mismatch always costs exactly 1 no matter which of the three operations gets picked.
Flip the recursion into a table filled bottom-up instead: dp[i][j] holds exactly what solve(i, j) computed, with an extra row and column for the base cases where one string has run out entirely — dp[i][0] = i (delete everything left) and dp[0][j] = j (insert everything left). Fill it forward — i from 1 to m, j from 1 to n — so that whenever a cell is being computed, the three cells it depends on (diagonally up-left, directly above, directly to the left) are already sitting in the table. On a match, dp[i][j] = dp[i-1][j-1] (carry the value, no cost); otherwise dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) (replace, delete, or insert — whichever is cheapest).
Walking it through:
dp[i][j] = edit distance between the first i characters of word1 and the first j characters of word2, for word1 = "stone" (rows) and word2 = "tore" (cols)
Turning the empty prefix of word1 into the first j characters of word2 takes j inserts; turning the first i characters of word1 into the empty prefix of word2 takes i deletes. These seed the table before any real character comparison happens.
No match, so dp[1][1] takes the cheapest of three neighbors — right now that's the diagonal (replace 's' with 't'). Keep watching: the actual best route through the table ends up skipping this cell entirely.
Row 1 finished filling in. This character matches, so the value carries straight from dp[1][0] = 1 — the delete-'s' cell from the base row, not dp[1][1]'s replace from the previous frame. Matches don't add cost; they just propagate whatever's already been paid.
Another match — 'o' lines up with 'o' — so the value keeps propagating unchanged: still 1.
First real mismatch on this route: replacing 'n' with 'r' is strictly cheapest here (the diagonal neighbor beats both up and left), so this is the one actual replace in the optimal script.
The last characters match too, so the final value carries straight from dp[4][3]: dp[5][4] = 2. Reading the route back: delete 's', keep 't' and 'o', replace 'n' with 'r', keep 'e' — "stone" → "tone" → "tore" in two operations.
Optimization
Dynamic programming (rolling rows)
Let dp[i][j] be the edit distance between the first i characters of word1 and the first j of word2. If the current characters match, carry dp[i-1][j-1]; otherwise take 1 + the minimum of replace (dp[i-1][j-1]), delete (dp[i-1][j]), and insert (dp[i][j-1]). Only the previous row is needed, so keep two rows.
O(m·n) time, O(min(m, n)) space (here O(n)).
function minDistance(word1, word2) {
const m = word1.length;
const n = word2.length;
// prev = dp[i - 1][...]: edit distance from the first (i - 1) chars of word1 to
// every prefix of word2. Row 0 is the base case: turning "" into word2[0:j] takes j inserts.
let prev = Array.from({ length: n + 1 }, (_, j) => j);
for (let i = 1; i <= m; i++) {
const curr = new Array(n + 1);
// dp[i][0]: turning word1[0:i] into "" takes i deletes.
curr[0] = i;
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
// Characters already match — carry the diagonal value, no extra cost.
curr[j] = prev[j - 1];
} else {
// Cheapest of: replace (diagonal), delete from word1 (above), insert into word1 (left).
curr[j] = 1 + Math.min(prev[j - 1], prev[j], curr[j - 1]);
}
}
// This row is done; it becomes "the row above" for the next iteration.
prev = curr;
}
return prev[n];
}Complexity analysis
Time complexity: O(m·n). Here's why:
- The fill computes exactly one value per cell of the conceptual
(m + 1) × (n + 1)dp table, one row at a time. - Each cell does O(1) work — one character comparison, then either a lookup (match) or a
minover three already-known cells (mismatch).
So the whole fill costs (m + 1)(n + 1) × O(1) = O(m·n) — down from the brute force's exponential O(3^(m+n)), since every (i, j) pair is now computed exactly once instead of re-derived by every insert/delete/replace path that happens to reach it.
Space complexity: O(n). Here's why:
- The stored solution keeps only two rows at a time —
prev(row i-1) andcurr(the row being built) — each of length n+1, sincedp[i][j]only ever reads the row directly above (prev[j-1],prev[j]) and the current row's previous cell (curr[j-1]). - Once a row finishes,
previs replaced bycurrand the old row is discarded — no history beyond one row back is kept.
That's O(n) rather than the full O(m·n) table a naively-materialized 2-D array would need. It could be tightened further to O(min(m, n)) by always rolling over the shorter string, but the stored solution keeps it simple and always rolls over word2's length.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| word1 = "", word2 = "" | 0 | Two empty strings — the forced base case, zero operations. |
| word1 = "", word2 = "cat" | 3 | word1 is empty — every character of word2 must be inserted. |
| word1 = "a", word2 = "z" | 1 | Single differing character each — the smallest case that needs a real operation, a single replace. |
| word1 = "xyz", word2 = "xyz" | 0 | Identical strings — already equal, so zero operations regardless of length. |
| word1 = "bbbb", word2 = "bb" | 2 | Repeated characters — every character already matches, so the distance collapses to just the length difference (two deletes); the DP mustn't overcount because of the repeats. |
| word1 = "ab", word2 = "ba" | 2 | Smallest case where replacing both characters (2 replaces) ties with a delete-then-insert route — both cost 2, so the DP just needs the minimum, not a single 'correct' script. |
Try it yourself
Write your solution against the real judge before checking the reference.