Skip to main content

54. Edit Distance

mediumAsked at Vercel

Find the minimum number of operations (insert, delete, replace) to transform word1 into word2. Vercel asks this for the canonical 2D DP — same recurrence shape as their config-diff and CRDT merge cost calculator.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; 2D DP expected.
  • Blind (2026-Q1)— Listed in Vercel runtime engineer screen.

Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character, Delete a character, Replace a character.

Constraints

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.

Examples

Example 1

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

Explanation: horse -> rorse -> rose -> ros.

Example 2

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

Approaches

1. Recursive without memo

ed(i, j) = 0 if both empty; otherwise 1 + min of insert, delete, replace.

Time
O(3^(m+n))
Space
O(m+n)
// Exponential. Memoize or go iterative.

Tradeoff: Demonstrates the recurrence; not viable past tiny inputs.

2. Bottom-up 2D DP (optimal)

dp[i][j] = edit distance for word1[0..i) and word2[0..j). dp[i][0] = i, dp[0][j] = j. If chars equal, dp[i][j] = dp[i-1][j-1]. Else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

Time
O(m*n)
Space
O(m*n)
function minDistance(word1, word2) {
  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;
  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], dp[i][j - 1], dp[i - 1][j - 1]);
    }
  }
  return dp[m][n];
}

Tradeoff: Classic 2D Levenshtein. Roll to O(min(m,n)) space using a 1D array if needed.

Vercel-specific tips

Vercel grades the 2D DP and the recurrence articulation. Bonus signal: stating the three operations correspond to three predecessors (delete = dp[i-1][j], insert = dp[i][j-1], replace = dp[i-1][j-1]) BEFORE coding. They may follow up with 'reconstruct the edit script' — backtrack from dp[m][n].

Common mistakes

  • Forgetting the base cases dp[i][0] = i and dp[0][j] = j — produces wrong answers near boundaries.
  • Off-by-one on word1[i-1] vs word1[i] — the DP is 1-indexed against 0-indexed strings.
  • Using Math.min on undefined cells (no boundary init).

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Reconstruct the edit script (which operations).
  • Weighted edit distance — different costs for insert/delete/replace.
  • Approximate string matching with a small edit-distance bound.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why three predecessors?

Each operation corresponds to one move in the dp grid: delete moves up (dp[i-1][j]), insert moves left (dp[i][j-1]), replace moves diagonally (dp[i-1][j-1]). Match also moves diagonally with no cost.

Can I do this in O(n) space?

Yes — keep only the previous row. Need a temporary scalar for the diagonal predecessor. Useful for very long strings.

Practice these live with InterviewChamp.AI

Drill Edit Distance and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →