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.
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:
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.
The entire DP hinges on one clean definition:
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.
dp[i-1][j-1] — both strings shrink by one (match or replace).dp[i-1][j] — word1 shrinks only ⇒ we deletedword1's char.dp[i][j-1] — word2 shrinks only ⇒ we insertedword2's char.dp[i][0] = i (delete all i chars to reach the empty string). dp[0][j] = j (insert all j chars from empty).dp[m][n].(m,n) following which neighbor produced each value — that recovers the actual operation sequence.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.
dp[i][j]= min edits to convert the first i chars of "horse" into the first j chars of "ros".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];
}(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.i prefix into "" costs i deletions; building a length-j prefix from "" costs j insertions. These seed the first row and column.dp[m][n] is the cost of aligning the full strings.dp[i-1][*] and dp[i][j-1]are already final when you read them. Reverse the loops and you'd read garbage.(m,n) choosing the neighbor that produced each value — exactly what the Visualize tab animates.1 + with per-op weights inside the min. The structure is unchanged.m + n − 2·LCS. Same grid, different recurrence.| convert string A to B with edits | 2D DP grid (m+1)×(n+1) |
| insert / delete / replace, minimize ops | Levenshtein recurrence |
| min cost over a pair of prefixes | dp[i][j] on prefix lengths |
| recover the actual operations | backtrace from (m,n) to (0,0) |
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];dp[i][j] mean?dp[i][j] represent?word1[i-1] === word2[j-1], what is dp[i][j]?dp[i-1][j] — corresponds to which operation?word1="horse", word2="ros", the edit distance is: