Skip to main content

72. Edit Distance

medium

Compute the minimum number of insertions, deletions, and substitutions to transform one string into another. The Levenshtein distance — the classic 2D DP on two strings, foundational to fuzzy-matching and spell-check.

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. 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), rorse -> rose (remove r), rose -> ros (remove e).

Example 2

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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1].

Hint 2

Base cases: dp[i][0] = i (delete all), dp[0][j] = j (insert all).

Hint 3

If word1[i-1] == word2[j-1], dp[i][j] = dp[i-1][j-1] (no op). Else dp[i][j] = 1 + min(dp[i-1][j] delete, dp[i][j-1] insert, dp[i-1][j-1] replace).

Solution approach

Reveal approach

Bottom-up 2D DP. Allocate dp[m+1][n+1]. Base row dp[0][j] = j (j inserts) and base column dp[i][0] = i (i deletes). For i = 1..m, j = 1..n: if word1[i-1] == word2[j-1], dp[i][j] = dp[i-1][j-1] (matching chars cost nothing). Else dp[i][j] = 1 + min(dp[i-1][j] [delete], dp[i][j-1] [insert], dp[i-1][j-1] [replace]). Return dp[m][n]. O(m * n) time, O(m * n) space; can be reduced to O(min(m, n)) with rolling rows.

Complexity

Time
O(m * n)
Space
O(m * n)

Related patterns

  • dynamic-programming
  • string-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta

Practice these live with InterviewChamp.AI

Drill Edit Distance and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →