Skip to main content

21. Edit Distance

hardAsked at Dropbox

Compute the minimum edits to transform one string into another — this is the theoretical backbone of Dropbox's diff-and-merge pipeline, used to reconcile two independently edited versions of a plain-text file.

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

Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. The allowed operations are: insert a character, delete a character, or replace a character.

Constraints

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

Examples

Example 1

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

Explanation: horse → rorse (replace h→r), rorse → rose (delete r), rose → ros (delete e).

Example 2

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

Approaches

1. Recursive with memoization

Define edit(i,j) as the minimum cost to align word1[i..] with word2[j..]. Recurse with three choices; cache results to avoid exponential blow-up.

Time
O(m*n)
Space
O(m*n)
function minDistance(word1, word2) {
  const m = word1.length;
  const n = word2.length;
  const memo = new Map();
  function dp(i, j) {
    if (i === m) return n - j;
    if (j === n) return m - i;
    const key = `${i},${j}`;
    if (memo.has(key)) return memo.get(key);
    let res;
    if (word1[i] === word2[j]) {
      res = dp(i + 1, j + 1);
    } else {
      res = 1 + Math.min(
        dp(i + 1, j),
        dp(i, j + 1),
        dp(i + 1, j + 1)
      );
    }
    memo.set(key, res);
    return res;
  }
  return dp(0, 0);
}

Tradeoff:

2. Bottom-up DP (2D table)

Build an (m+1)×(n+1) table where dp[i][j] = min edits to convert word1[0..i-1] to word2[0..j-1]. Fill row by row; each cell depends on its top, left, and top-left neighbors.

Time
O(m*n)
Space
O(m*n), optimizable to O(n)
function minDistance(word1, word2) {
  const m = word1.length;
  const n = word2.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++) {
      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:

Dropbox-specific tips

Dropbox frequently extends this to three-way merges (two edits from a common ancestor). Walk through how the DP table encodes each of the three operations and be ready to discuss the space optimization — rolling two rows instead of the full grid — since Dropbox engineers care about memory efficiency in the sync client.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →