9.6 Edit Distance

Demo: Edit Distance — LC 72 (Hard — Google/Microsoft High)

Statement (Demo): Given word1 and word2, return the minimum number of operations (insert, delete, replace a character) to turn word1 into word2. Example: word1="horse", word2="ros" → 3 (replace h→r, delete r, delete e) | ⚡ len(word1), len(word2) ≤ 500

Approach: dp[i][j] = cost to turn the first i characters of word1 into the first j of word2. Matching characters cost nothing (diagonal); otherwise 1 + the min of replace/delete/insert. Base cases: empty string → j inserts or i deletes.

function minDistance(w1, w2) {
  const m = w1.length,
    n = w2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)),
  );
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] =
        w1[i - 1] === w2[j - 1]
          ? dp[i - 1][j - 1]
          : 1 +
            Math.min(
              dp[i - 1][j - 1], // replace
              dp[i - 1][j], // delete
              dp[i][j - 1], // insert
            );
  return dp[m][n];
}

Complexity: Time O(m·n), Space O(m·n)