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 Sam K., 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

More Dynamic Programming practice problems

See all Dynamic Programming problems →