Skip to main content

56. Edit Distance

mediumAsked at Snowflake

Compute the minimum edit distance between two strings (insert/delete/replace). Snowflake asks this because it's the canonical 2D-DP — and because their fuzzy-match (Jaro-Winkler, Levenshtein) UDF is built on the same recurrence.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake function-development team uses this to anchor fuzzy-match UDF discussion.
  • LeetCode Discuss (2025-11)— Reported at Snowflake SDE-I screens.

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 (replace h with r) -> rose (delete r) -> ros (delete e).

Example 2

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

Approaches

1. Recursive without memo

edit(i,j) = if chars match: edit(i-1, j-1); else 1 + min(edit(i-1, j), edit(i, j-1), edit(i-1, j-1)).

Time
O(3^(m+n))
Space
O(m+n)
// outline only — exponential.

Tradeoff: Exponential. Mention to reject.

2. 2D DP table (optimal)

dp[i][j] = edit distance for word1[:i] and word2[:j]. Base: dp[i][0] = i, dp[0][j] = j. Transition: same as recursion.

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: O(mn) time and space. Can be optimized to O(min(m,n)) space using rolling row.

Snowflake-specific tips

Snowflake interviewers want the three transitions stated cleanly: insert (dp[i][j-1]+1), delete (dp[i-1][j]+1), replace (dp[i-1][j-1]+1). Bonus signal: discuss the rolling-row O(min(m,n)) space optimization and how it would work for streaming long strings inside a UDF call.

Common mistakes

  • Off-by-one between dp index i and word1 index i-1.
  • Confusing which of dp[i-1][j], dp[i][j-1], dp[i-1][j-1] maps to insert/delete/replace.
  • Skipping the base case initialization of dp[i][0] and dp[0][j].

Follow-up questions

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

  • Space-optimized to O(n).
  • Hirschberg's algorithm (linear space + traceback).
  • How would you implement Snowflake's EDITDISTANCE UDF?

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 transitions?

To convert word1[:i] to word2[:j]: delete (use word1[:i-1] -> word2[:j]), insert (use word1[:i] -> word2[:j-1]), or replace (use word1[:i-1] -> word2[:j-1]). Min of the three +1 (or 0 if last chars match).

How does Snowflake EDITDISTANCE work?

Internally the same DP, optimized to O(n) space with rolling row. For very long strings it can spill to disk; Hirschberg's algorithm is a CPU-time/memory trade-off for that case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →