Dynamic Programming crash course ↗ · 60

72. Edit Distance

Convert one string into another using insert, delete, and replace — minimize the number of edits (Levenshtein distance). The archetypal 2D dynamic program: a table where every cell leans on three neighbors, and the answer crystallizes in the bottom-right corner.

● Hard2D Dynamic ProgrammingString AlignmentTypeScript

PROBLEM What we're solving

Given word1 = "horse" and word2 = "ros", return the minimum number of single-character edits to turn the first into the second. Three operations, each cost 1:

  • Insert a character
  • Delete a character
  • Replace a character

For "horse" → "ros" the answer is 3: replace h→r, delete r, delete e. This metric — Levenshtein distance — powers spell-check, DNA alignment, and diff tools.

KEY IDEA Define the subproblem precisely

The entire DP hinges on one clean definition:

dp[i][j] = the minimum edits to convert the first i characters of word1 into the first j characters of word2.

The full answer is dp[m][n]. To build it we ask: what's the last operation that aligns word1[i-1] with word2[j-1]? It must be exactly one of four cases — and each points to a smaller, already-solved subproblem.

RECURRENCE Each cell leans on three neighbors

# if the two current characters are equal — a free ride:
dp[i][j] = dp[i-1][j-1] ← diagonal, no cost

# otherwise, pay 1 and take the cheapest of three moves:
dp[i][j] = 1 + min(
  dp[i-1][j-1], ← replace
  dp[i-1][j], ← delete from word1
  dp[i][j-1] ← insert into word1
)
  • Diagonal dp[i-1][j-1] — both strings shrink by one (match or replace).
  • Up dp[i-1][j] — word1 shrinks only ⇒ we deletedword1's char.
  • Left dp[i][j-1] — word2 shrinks only ⇒ we insertedword2's char.
The classic confusion →"up = delete, left = insert." Moving up consumes a char of word1 without consuming word2, so word1 must lose a char (delete). Moving left consumes a char of word2 with nothing from word1, so we must have added one (insert).

BASE & ORDER Where it starts, how it flows

  • Base cases. dp[i][0] = i (delete all i chars to reach the empty string). dp[0][j] = j (insert all j chars from empty).
  • Fill order. Row by row, left to right — guaranteeing the three neighbors (up, left, diagonal) are always ready before the current cell.
  • Answer. Bottom-right corner dp[m][n].
  • Reconstruct the edits. Backtrace from (m,n) following which neighbor produced each value — that recovers the actual operation sequence.

COST Complexity & the space trick

Naive recursion
O(3m+n)
Branches into 3 at every mismatch. Exponential.
Tabulated DP
O(m·n)
Each of (m+1)(n+1) cells computed once.

Space: O(m·n) → O(min(m,n))

Each row depends only on the current and previous row, so you can keep just two rows (or one row + a saved diagonal) and roll them — dropping space to O(min(m,n)). The tradeoff: you lose the full table needed to backtrace the edit sequence. Keep the whole table when the interviewer asks for the operations.

Pattern transfer → the same (m+1)×(n+1) grid solves Longest Common Subsequence, Distinct Subsequences, Interleaving String, and Regular Expression Matching. Edit Distance is the gateway DP.

RUN IT Fill the table, then trace the edits

step 0 / 38
STARTAllocate a 6×4 table. dp[i][j]= min edits to convert the first i chars of "horse" into the first j chars of "ros".
1▶function minDistance(word1: string, word2: string): number {
2▶  const m = word1.length, n = word2.length;
3  // dp[i][j] = min edits to turn word1[0..i) into word2[0..j)
4▶  const dp: number[][] = Array.from({ length: m + 1 }, () =>
5▶    new Array(n + 1).fill(0));
6 
7  // base cases: convert to / from the empty string
8  for (let i = 0; i <= m; i++) dp[i][0] = i;
9  for (let j = 0; j <= n; j++) dp[0][j] = j;
10 
11  for (let i = 1; i <= m; i++) {
12    for (let j = 1; j <= n; j++) {
13      if (word1[i - 1] === word2[j - 1]) {
14        dp[i][j] = dp[i - 1][j - 1];        // match → free
15      } else {
16        dp[i][j] = 1 + Math.min(
17          dp[i - 1][j - 1],   // replace
18          dp[i - 1][j],       // delete from word1
19          dp[i][j - 1]        // insert into word1
20        );
21      }
22    }
23  }
24  return dp[m][n];
25}
ε
r
o
s
ε
h
o
r
s
e
Loop indices
i: —
j: —
Current computation
waiting…
Edit sequence
revealed during backtrace
current cellneighbor it depends onoptimal edit path
slowfast

TYPESCRIPT The solution, annotated

minDistance.ts
function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  // dp[i][j] = min edits to turn word1[0..i) into word2[0..j)
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0));

  // base cases: convert to / from the empty string
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];        // match → free
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j - 1],   // replace
          dp[i - 1][j],       // delete from word1
          dp[i][j - 1]        // insert into word1
        );
      }
    }
  }
  return dp[m][n];
}

Reading it block by block

Lines 4–5 — the table. An (m+1) × (n+1) matrix. The +1 reserves row 0 and column 0 for the empty-string base cases — the trick that makes the recurrence uniform with no special-casing inside the loop.
Lines 8–9 — base cases. Turning a length-i prefix into "" costs i deletions; building a length-j prefix from "" costs j insertions. These seed the first row and column.
Lines 13–14 — the match shortcut.When the current characters are equal, no edit is needed at this position; inherit the diagonal directly. This is what lets shared subsequences "ride for free."
Lines 16–20 — the mismatch. Pay 1 edit, then take the best of three smaller problems. Each branch corresponds to a concrete operation: diagonal = replace, up = delete, left = insert.
Line 24 — the answer. By definition, dp[m][n] is the cost of aligning the full strings.
Complexity → Iteration order matters → filling row-by-row, left-to-right guarantees dp[i-1][*] and dp[i][j-1]are already final when you read them. Reverse the loops and you'd read garbage.

INTERVIEWFollow-ups they'll ask

  • "Reduce the space." Keep two rows (prev, curr) and swap each iteration → O(min(m,n)) space. Mention you lose backtrace ability.
  • "Return the actual edits, not just the count." Keep the full table, then backtrace from (m,n) choosing the neighbor that produced each value — exactly what the Visualize tab animates.
  • "Different operation costs?" Replace the 1 + with per-op weights inside the min. The structure is unchanged.
  • "How does this relate to LCS?" With only insert/delete allowed (no replace), min edits = m + n − 2·LCS. Same grid, different recurrence.

OPTIMAL 2D Dynamic Programming

minDistance.ts
function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  // dp[i][j] = min edits to turn word1[0..i) into word2[0..j)
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0));

  // base cases: convert to / from the empty string
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];        // match → free
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j - 1],   // replace
          dp[i - 1][j],       // delete from word1
          dp[i][j - 1]        // insert into word1
        );
      }
    }
  }
  return dp[m][n];
}
Complexity → Iteration order matters → filling row-by-row, left-to-right guarantees dp[i-1][*] and dp[i][j-1]are already final when you read them. Reverse the loops and you'd read garbage.

ALT 1 Space-optimized DP (two rows)

O(m·n) time · O(min(m,n)) space

Same recurrence, but only the previous and current rows are ever needed — roll them to collapse the table down to a single row plus a saved diagonal.

approach-2.ts
function minDistance(word1: string, word2: string): number {
  // Iterate over the longer string in the outer loop so the
  // rolling rows have length min(m, n) + 1 — minimal space.
  if (word1.length < word2.length) {
    [word1, word2] = [word2, word1];
  }
  const m = word1.length, n = word2.length;

  // prev[j] = edits to turn word1[0..i-1) into word2[0..j)
  let prev: number[] = Array.from({ length: n + 1 }, (_, j) => j);

  for (let i = 1; i <= m; i++) {
    const curr: number[] = new Array<number>(n + 1);
    curr[0] = i; // delete i chars of word1 to reach the empty prefix
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        curr[j] = prev[j - 1];            // match → diagonal, free
      } else {
        curr[j] = 1 + Math.min(
          prev[j - 1],   // replace (diagonal)
          prev[j],       // delete  (up)
          curr[j - 1]    // insert  (left)
        );
      }
    }
    prev = curr; // roll: this row becomes the previous row
  }
  return prev[n];
}
Note → The diagonal dp[i-1][j-1] lives at prev[j-1], the up neighbor at prev[j], and the left neighbor at the freshly written curr[j-1] — read order matters. This trades away the full table, so you can no longer backtrace the actual edit sequence.

ALT 2 Top-down recursion + memo

O(m·n) time · O(m·n) space

Recurse on the suffix lengths (i, j) and cache each result — the same recurrence read top-down, often the easiest version to derive on the spot.

approach-3.ts
function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  // memo[i][j] = edits to turn word1[i..) into word2[j..); -1 = unset
  const memo: number[][] = Array.from({ length: m + 1 }, () =>
    new Array<number>(n + 1).fill(-1));

  function solve(i: number, j: number): number {
    // one string exhausted → insert or delete the rest
    if (i === m) return n - j;
    if (j === n) return m - i;
    if (memo[i][j] !== -1) return memo[i][j];

    let result: number;
    if (word1[i] === word2[j]) {
      result = solve(i + 1, j + 1);          // match → consume both, free
    } else {
      result = 1 + Math.min(
        solve(i + 1, j + 1),  // replace
        solve(i + 1, j),      // delete from word1
        solve(i, j + 1)       // insert into word1
      );
    }
    memo[i][j] = result;
    return result;
  }

  return solve(0, 0);
}
Note → Only reachable (i, j) pairs get computed, but worst case fills the whole memo so the bound matches the table. Recursion depth is O(m + n) — for very long strings the bottom-up versions avoid any stack-overflow risk.

ALT 3 Brute force — naive recursion, no memo

O(3^(m+n)) time · O(m + n) space

The same recurrence, but with no cache: on a mismatch try all three of insert, delete, and replace and take the cheapest. A correctness baseline before adding memoisation.

approach-4.ts
function minDistance(word1: string, word2: string): number {
  function solve(i: number, j: number): number {
    // One string exhausted → insert or delete whatever's left.
    if (i === word1.length) return word2.length - j;
    if (j === word2.length) return word1.length - i;

    if (word1[i] === word2[j]) {
      return solve(i + 1, j + 1);            // match → consume both, free
    }
    return 1 + Math.min(
      solve(i + 1, j + 1),  // replace
      solve(i + 1, j),      // delete from word1
      solve(i, j + 1)       // insert into word1
    );
  }

  return solve(0, 0);
}
Note → Each mismatch fans out into three recursive calls, so the call tree is exponential — O(3^(m+n)) and unusable beyond tiny strings. Every overlapping (i, j) pair is recomputed many times; caching them (the memoised version above) drops it to O(m·n).

MNEMONIC The one-liner

Match rides the diagonal free; a mismatch pays one and takes the cheapest neighbor.

TRIGGERS When you see ___ → reach for ___

convert string A to B with edits2D DP grid (m+1)×(n+1)
insert / delete / replace, minimize opsLevenshtein recurrence
min cost over a pair of prefixesdp[i][j] on prefix lengths
recover the actual operationsbacktrace from (m,n) to (0,0)

SKELETON The reusable shape

skeleton.ts
const m = word1.length, n = word2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) dp[i][0] = i;   // base: delete-to-empty
for (let j = 0; j <= n; j++) dp[0][j] = j;   // base: insert-from-empty
for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {
    if (word1[i - 1] === word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
    else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
  }
}
return dp[m][n];

FLASHCARDS Tap to flip

What does dp[i][j] mean?
The minimum edits to convert the first i characters of word1 into the first j characters of word2.
tap to flip
1 / 6
Answer to reveal explanations. No penalty for retries.Score: 0 / 8
QUESTION 01
What does dp[i][j] represent?
QUESTION 02
When word1[i-1] === word2[j-1], what is dp[i][j]?
QUESTION 03
On a mismatch, the cell above — dp[i-1][j] — corresponds to which operation?
QUESTION 04
What are the base cases?
QUESTION 05
Time and space complexity of the tabulated solution?
QUESTION 06
For word1="horse", word2="ros", the edit distance is:
QUESTION 07
#72 · Edit DistanceFind the minimum number of insert, delete, and replace edits to convert one string into another (Levenshtein distance) with a 2D dynamic-programming table whose answer lands in the bottom-right corner.Which algorithmic approach does this primarily use?
QUESTION 08
#72 · Edit DistanceFind the minimum number of insert, delete, and replace edits to convert one string into another (Levenshtein distance) with a 2D dynamic-programming table whose answer lands in the bottom-right corner.Which implementation correctly solves it?