4.24.9 — Edit Distance

LeetCode 72 · Hard · ★ Blind 75

The problem

Return the minimum number of operations to turn word1 into word2. The allowed operations are insert, delete and replace, each costing 1.

"horse" → "ros"        →  3     (replace h→r, delete r, delete e)
"intention" → "execution"  →  5

The pattern

Two strings, so a grid. Let dp[i][j] be the edit distance between the first i characters of word1 and the first j of word2.

Look at the last character of each prefix.

If they match, that character costs nothing — align it and move both back:

dp[i][j] = dp[i-1][j-1]

If they differ, you must pay 1 and then do one of three things. All three are available and you take the cheapest:

dp[i][j] = 1 + \min\big(\underbrace{dp[i-1][j-1]}_{\text{replace}},\ \underbrace{dp[i-1][j]}_{\text{delete}},\ \underbrace{dp[i][j-1]}_{\text{insert}}\big)

Reading the three terms is the whole problem, so read them carefully:

• Replace — change word1[i-1] into word2[j-1]. Both characters are now dealt with, so both indices go back one.
• Delete — remove word1[i-1]. That character is gone, so i goes back one and j stays; you still owe word2's j characters.
• Insert — insert word2[j-1] at the end of word1. That satisfies word2's character, so j goes back one and i stays.

The direction of the index that moves is the direction of the operation. If you can say which index moves and why, you will never mix the three up.

The base cases, which are not zero

dp[i][0] = i — turning a prefix of length i into the empty string takes i deletions.

dp[0][j] = j — building a prefix of length j from nothing takes j insertions.

This is the first two-string DP in the chapter whose base row and column are not all zeros, and getting them wrong is the usual failure.

The solution

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m + 1):
            dp[i][0] = i                      # delete everything
        for j in range(n + 1):
            dp[0][j] = j                      # insert everything

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]           # free
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j - 1],  # replace
                                       dp[i - 1][j],      # delete
                                       dp[i][j - 1])      # insert

        return dp[m][n]

TypeScript

function minDistance(word1: string, word2: string): number {
  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 - 1], dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

Trace

"horse" to "ros":

        ''  r  o  s
   ''    0  1  2  3
    h    1  1  2  3
    o    2  2  1  2
    r    3  2  2  2
    s    4  3  3  2
    e    5  4  4  3

The answer 3 sits in the corner. Follow it backwards: e deleted, s matched, r deleted… and one replacement of h with r near the start — three operations, matching the problem statement.

Space optimisation

The recurrence reads only the previous row and the cell to the left, so two rows suffice:

prev = list(range(n + 1))
for i in range(1, m + 1):
    curr = [i] + [0] * n
    for j in range(1, n + 1):
        if word1[i-1] == word2[j-1]:
            curr[j] = prev[j-1]
        else:
            curr[j] = 1 + min(prev[j-1], prev[j], curr[j-1])
    prev = curr
return prev[n]

curr[0] = i is the base case for this row and must be set before the inner loop.

O(n) space, and it is the version real implementations use.

Complexity

O(mn) time, O(mn) or O(n) space.

There is a faster algorithm when the distance is small — Ukkonen's, O(m \times d) for distance d — which only fills a band around the diagonal. Worth naming; not worth writing.

This one is genuinely everywhere

Edit distance is called Levenshtein distance, and it is the most widely used algorithm in this chapter:

• Spell checkers — rank candidate corrections by edit distance from what you typed.
• diff and git diff — the same grid on lines instead of characters, which is 4.24.2's relative.
• DNA sequence alignment — Needleman-Wunsch is this algorithm with per-operation costs instead of 1, and it is one of the foundations of computational biology.
• Fuzzy search — "did you mean" and typo-tolerant matching in search engines.
• OCR and speech recognition scoring — word error rate is edit distance on word sequences.

Mentioning one of these is a strong finish, because it shows the algorithm is a tool rather than a puzzle.

Where this goes next

• One Edit Distance — is the distance exactly 1? Answerable in O(n) with two pointers and no table, because you can stop after the first mismatch.
• Delete Operation for Two Strings — deletions only, so the answer is m + n − 2 × LCS.
• Minimum ASCII Delete Sum — the same grid with character costs instead of 1, which is exactly the Needleman-Wunsch generalisation.

What the interviewer will push on

"Explain the three operations in terms of the indices." Which index moves, and why. If you can do this, the recurrence is not memorised.

"What are the base cases?" i deletions and j insertions — not zero.

"Why is a match free?" No operation is needed; just align the two characters.

"Can you use O(n) space?" Two rows, remembering to set the new row's first cell.

"How would you recover the actual edit script?" Keep the full table and walk backwards from the corner, at each step seeing which of the four predecessors produced the value. Reconstruction needs the table, which is the standing cost of the space optimisation.

"Where is this used?" Spell check, diff, DNA alignment.

One thing to volunteer: name it as Levenshtein distance and give one real use. It reframes the problem from an exercise into something you would reach for.

Next: 4.24.10 Burst Balloons — the hardest DP in the set, and one where the obvious state definition is simply wrong.