Edit Distance

Examples

Input: word1 = "horse", word2 = "ros"
Output: 3

horse -> rorse (replace 'h' with 'r') -> rose (delete 'r') -> ros (delete 'e').

Input: word1 = "intention", word2 = "execution"
Output: 5

Constraints

• 0 <= word1.length, word2.length <= 500

• Both words contain only lowercase English letters

Approach

Build a table where cell (i, j) means: "the minimum number of edits to turn the first i characters of word1 into the first j characters of word2."

If those two characters already match, this position costs nothing — the answer is exactly the answer for one character back in both words, (i-1, j-1). If they don't match, one edit must happen here, and it's worth 1 plus the cheapest of the three options: delete word1's character ((i-1, j)), insert a character to match word2's ((i, j-1)), or replace word1's character with word2's ((i-1, j-1)).

The base cases handle turning a string into an empty one (or vice versa): turning the first i characters of word1 into nothing takes i deletions, and turning nothing into the first j characters of word2 takes j insertions.

Solutions

Brute Force — Recursion

Walk both words from the front. If the current characters match, move both forward for free. Otherwise, try all three edit types and recurse, taking whichever leads to fewer total edits.

function minDistance(word1, word2) {
  function solve(i, j) {
    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);

    const insert = 1 + solve(i, j + 1);
    const remove = 1 + solve(i + 1, j);
    const replace = 1 + solve(i + 1, j + 1);
    return Math.min(insert, remove, replace);
  }

  return solve(0, 0);
}

Time: O(3^(m + n)) in the worst case · Space: O(m + n) — recursion depth

Optimal — Bottom-Up 2D Table

Build a table over (prefix length of word1, prefix length of word2). Seed row 0 and column 0 with the all-insert / all-delete base cases, then fill the rest using the match/no-match rule.

function minDistance(word1, word2) {
  const m = word1.length;
  const n = word2.length;
  const table = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 0; i <= m; i++) table[i][0] = i; // delete all i characters of word1
  for (let j = 0; j <= n; j++) table[0][j] = j; // insert all j characters of word2

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        table[i][j] = table[i - 1][j - 1];
      } else {
        table[i][j] = 1 + Math.min(
          table[i - 1][j],     // delete
          table[i][j - 1],     // insert
          table[i - 1][j - 1]  // replace
        );
      }
    }
  }

  return table[m][n];
}

Time: O(m * n) · Space: O(m * n)