Skip to main content

56. Edit Distance

hardAsked at Ola

Find the minimum edit distance between two strings.

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, delete, and replace a character.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Recursive

Try insert/delete/replace at each mismatch.

Time
O(3^(m+n))
Space
O(m+n)
// raw recursion; exponential

Tradeoff:

2. DP table

dp[i][j] = min ops to convert word1[0..i] to word2[0..j]; transitions on match or three edit moves.

Time
O(m*n)
Space
O(m*n)
function minDistance(a, b) {
  const m = a.length, n = b.length;
  const dp = 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 (a[i-1] === b[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:

Ola-specific tips

Ola interviewers ask edit-distance to test classic DP scaffolding; tie it to scoring near-duplicate address strings during pickup-location dedup.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →