The problem. Given two words, return the fewest operations that turn word1 into word2. Each operation inserts, deletes or replaces one letter.
word1 = "horse", word2 = "ros" -> 3 (replace h with r, delete r, delete e)
word1 = "intention", word2 = "execution" -> 5
word1 = "cat", word2 = "cut" -> 1 (replace a with u)Use the same table as Longest Common Subsequence: dp[i][j] is the fewest edits that turn the first i letters of word1 into the first j letters of word2. Look at the last letter of each prefix.
If they're equal, they cost nothing: dp[i][j] = dp[i-1][j-1]. If they differ, the last step of the best edit sequence is one of three moves, each leaving a smaller question: replace the letter (then turn i - 1 letters into j - 1: the diagonal), delete it (turn i - 1 letters into j: above), or insert word2's letter (turn i letters into j - 1: left). Take 1 plus the cheapest. The edges are i deletes (column 0) and j inserts (row 0).
function minDistance(word1, word2) { const edit = (i, j) => { // edits to turn word1[i..] into word2[j..] if (i === word1.length) return word2.length - j; // insert the rest if (j === word2.length) return word1.length - i; // delete the rest if (word1[i] === word2[j]) return edit(i + 1, j + 1); return 1 + Math.min(edit(i + 1, j + 1), edit(i + 1, j), edit(i, j + 1)); // replace, delete, insert }; return edit(0, 0);}Time O(3ⁿ⁺ᵐ) in the worst case, space O(n + m) for the call stack. Every mismatch branches three ways, and the same (i, j) pairs come up again and again — a memo turns it into the table below.
A matching letter copies the diagonal; otherwise take one edit plus the cheapest of replace, delete or insert.
function minDistance(word1, word2) { const n = word1.length, m = word2.length; // dp[i][j]: the fewest edits to turn word1[0..i) into word2[0..j) const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0)); for (let i = 0; i <= n; i++) dp[i][0] = i; // delete all i letters for (let j = 0; j <= m; j++) dp[0][j] = j; // insert all j letters for (let i = 1; i <= n; i++) { for (let j = 1; j <= m; j++) { if (word1[i - 1] === word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; // last letters match: free else dp[i][j] = 1 + Math.min( dp[i - 1][j - 1], // replace word1[i-1] with word2[j-1] dp[i - 1][j], // delete word1[i-1] dp[i][j - 1] // insert word2[j-1] ); } } return dp[n][m];}Time O(n · m), space O(n · m). Walking back from the bottom-right cell — following whichever neighbour gave each value — lists one shortest sequence of edits, as the simulator's last step shows.
As with LCS, each row only needs the one above it. The one new detail: row 0 starts as 0, 1, 2, … and each new row starts with i, the cost of deleting i letters.
function minDistance(word1, word2) { const m = word2.length; let prev = Array.from({ length: m + 1 }, (_, j) => j); // row 0: insert j letters for (let i = 1; i <= word1.length; i++) { const cur = [i]; // column 0: delete i letters for (let j = 1; j <= m; j++) { cur[j] = word1[i - 1] === word2[j - 1] ? prev[j - 1] : 1 + Math.min(prev[j - 1], prev[j], cur[j - 1]); // replace, delete, insert } prev = cur; } return prev[m];}Time O(n · m), space O(m) — or O(min(n, m)) by putting the shorter word along the rows, since the distance is the same in both directions.
Edit distance is LCS with costs: the same table, the same last-letter reasoning, one more move. Spell checkers, DNA alignment and diff all run on this table.
"cat" and "cut": one replace, not a delete plus an insert."a" and "abcdef": the edge row and column carry most of the cost.0, 1, 2, …, not zeros: that's the difference from LCS.Was this helpful?