Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtwo-dimensional-dp

Edit Distance

Problem (restated)

Convert word1 to word2 using insert, delete, or replace (each cost 1). Return the minimum number of operations.

Intuition

dp[i][j] = min ops for prefixes word1[:i] and word2[:j]. Match copies the diagonal; otherwise take the best of delete, insert, or replace plus one.

Approaches

Classic Levenshtein DP

Tested only

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

Idea. Full table. Base: dp[i][0]=i, dp[0][j]=j. Equal chars → diagonal; else 1 + min of three neighbors.

Walkthrough. "horse" → "ros" needs 3 operations.

Trade-offs. Clearest recurrence; uses full O(mn) memory.

Solution

export function minDistance(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  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]!;
      } else {
        dp[i]![j] =
          1 + Math.min(dp[i - 1]![j - 1]!, dp[i - 1]![j]!, dp[i]![j - 1]!);
      }
    }
  }
  return dp[m]![n]!;
}

export function minDistance(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  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]!;
      } else {
        dp[i]![j] =
          1 + Math.min(dp[i - 1]![j - 1]!, dp[i - 1]![j]!, dp[i]![j - 1]!);
      }
    }
  }
  return dp[m]![n]!;
}

Rolling row DP

Tested only

Time O(m·n)Space O(min(m,n))

Idea. Keep only the previous row. Optionally put the shorter word on the column axis.

Trade-offs. Same time, linear space. Learn the 2D table first, then compress.

Solution

/** Space-optimized edit distance: one rolling row O(min(m,n)). */
export function minDistanceRolling(word1: string, word2: string): number {
  if (word1.length < word2.length) [word1, word2] = [word2, word1];
  const m = word1.length, n = word2.length;
  let prev = Array.from({ length: n + 1 }, (_, j) => j);
  for (let i = 1; i <= m; i++) {
    const cur = new Array<number>(n + 1);
    cur[0] = i;
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) cur[j] = prev[j - 1]!;
      else cur[j] = 1 + Math.min(prev[j]!, cur[j - 1]!, prev[j - 1]!);
    }
    prev = cur;
  }
  return prev[n]!;
}

/** Space-optimized edit distance: one rolling row O(min(m,n)). */
export function minDistanceRolling(word1: string, word2: string): number {
  if (word1.length < word2.length) [word1, word2] = [word2, word1];
  const m = word1.length, n = word2.length;
  let prev = Array.from({ length: n + 1 }, (_, j) => j);
  for (let i = 1; i <= m; i++) {
    const cur = new Array<number>(n + 1);
    cur[0] = i;
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) cur[j] = prev[j - 1]!;
      else cur[j] = 1 + Math.min(prev[j]!, cur[j - 1]!, prev[j - 1]!);
    }
    prev = cur;
  }
  return prev[n]!;
}

Template connection

Two-string alignment DP (same family as LCS).

Deep dive

Match: dp[i][j] = dp[i-1][j-1]
Else: 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (delete / insert / replace)

Reflection

How do LCS and edit distance relate?
What breaks if you forget the base row/column?