p60 — Edit Distance

Source: LeetCode 72 · Hard · Topics: 2D DP, String DP Companies (2024–2025): Google (very high), Apple (high), Meta (high), Amazon (high), Microsoft (high) Loop position: The canonical Hard DP. Levenshtein distance underpins spell-checkers, DNA alignment, git diff, autocorrect. Bar Raiser favorite.

1. Quick Context

Given word1, word2, return min operations (insert, delete, substitute — each cost 1) to convert word1 → word2.

dp[i][j] = edit distance between word1[:i] and word2[:j]
if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]
else: dp[i][j] = 1 + min(dp[i-1][j-1],  # substitute
                         dp[i-1][j],    # delete from word1
                         dp[i][j-1])    # insert into word1
dp[i][0] = i; dp[0][j] = j

O(m·n) time, O(min(m,n)) space possible with prev_diag trick.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/edit-distance/

STOP. 25-min timer.

3. Prerequisite Concepts

  • LCS (p59) — same DP skeleton.
  • 2D DP grid; prefix-length indexing.
  • Three-way min over neighbors.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Minimum-cost edit script (insert/delete/substitute) to turn one string into another.

2. Clarify: All ops cost 1? (Yes on LC.) Strings only lowercase? Length up to 500 on LC.

3. Examples:

  • ("horse", "ros") → 3: horse → rorse (sub h→r) → rose (del r) → ros (del e).
  • ("intention", "execution") → 5.

5. Brute force: Recurse on prefixes, 3 transitions each; exponential without memo.

6. Target: O(m·n) DP.

7. Pattern: 2D string DP with three transitions (vs LCS’s two).

8. Develop: see solution.py.

9. Test: empty strings; identical; one empty; LC examples; all-substitutes; all-inserts.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 The recurrence — interpreting the three transitions

Reading dp[i][j] = “min ops to convert word1[:i] to word2[:j]”:

  • dp[i-1][j-1] + 1 (“substitute”): handle the last pair as a substitution.
  • dp[i-1][j] + 1 (“delete”): drop word1[i-1], then convert remaining word1[:i-1] to word2[:j].
  • dp[i][j-1] + 1 (“insert”): convert word1[:i] to word2[:j-1], then insert word2[j-1].

If word1[i-1] == word2[j-1]: no operation needed at this step; dp[i][j] = dp[i-1][j-1]. (Equivalent to “free substitute”.)

6.2 Base cases

  • dp[0][j] = j: empty → first j chars of word2 needs j insertions.
  • dp[i][0] = i: first i chars of word1 → empty needs i deletions.

These are NOT zeros; getting them wrong silently corrupts answers.

6.3 Why three transitions suffice

Any edit script can be normalized to a sequence of (insert | delete | substitute) operations on a left-to-right scan. The DP enumerates the operation applied to the last position; recursion handles the rest. Optimality proved by induction.

6.4 Symmetry

edit(a, b) = edit(b, a) because every insert in one direction = delete in the other (and substitute is its own inverse). So we can swap to put the shorter string on the inner loop for cache friendliness.

6.5 Space compression

Same prev_diag trick as LCS (p59 §6.3):

prev_diag = dp[0]       # which is i at start of row i
dp[0] = i               # base case for this row
for j in 1..n:
    tmp = dp[j]
    if word1[i-1] == word2[j-1]:
        dp[j] = prev_diag
    else:
        dp[j] = 1 + min(prev_diag, dp[j], dp[j-1])
    prev_diag = tmp

6.6 Damerau–Levenshtein variant

Add a fourth transition: transposition of adjacent characters (cost 1). For positions i, j: if word1[i-1] == word2[j-2] and word1[i-2] == word2[j-1] (i.e., the last two chars are swapped), allow dp[i-2][j-2] + 1.

Used in typo-tolerant search (“teh” → “the”). Real-world spellcheckers (e.g., Apache Lucene) use this.

6.7 Connection to LCS (p59)

When substitution is disallowed (insert/delete only, each cost 1), edit(a, b) = m + n - 2·lcs(a, b). With substitution, edit distance is ≤ that bound (because substitute is sometimes cheaper than insert+delete).

6.8 Weighted variants

In production:

  • Insertions and deletions may cost differently (e.g., DNA alignment: gap-opening cost vs gap-extension cost — affine gap penalties, solved by Gotoh’s algorithm in O(m·n) with 3 DP tables).
  • Substitutions may be weighted by a similarity matrix (BLOSUM62 in bioinformatics).

LeetCode 72 uses uniform cost 1. Mention these variants for Senior+ signal.

6.9 Hirschberg’s algorithm — O(min(m,n)) space + reconstruction

For huge strings where you need the actual edit script (not just length), naive backtrack requires the full O(m·n) table. Hirschberg’s divide-and-conquer computes the alignment in O(m·n) time and O(min(m,n)) space. Used in diff tools where memory matters.

7. Anti-Pattern Analysis

  1. Forget base cases dp[i][0] = i, dp[0][j] = j — use zeros, get wildly wrong answers.
  2. Add +1 in the match case — should be dp[i-1][j-1] with no +1.
  3. Confuse “insert into word1” vs “into word2” — they’re symmetric in effect, but interpreting transitions inconsistently breaks reasoning under follow-up questions.
  4. Two transitions instead of three — student remembers only “diagonal or one side”; missing the substitute, undercounts edits.
  5. 1D compression without prev_diag — corrupts substitute transition.
  6. Compute only the value, can’t print the edit script — Senior+ will ask.

8. Skills & Takeaways

  • 2D DP with three-way min — generalizes to many alignment problems.
  • Base-case discipline (the i/j initial row/col).
  • Match-then-free-substitute interpretation.
  • Space compression with prev_diag.
  • Damerau, Hirschberg, Gotoh — extension landscape.

9. When to Move On

  • Implement O(m·n) cold in 15 min including base cases.
  • Compress to 1D space.
  • Print the edit script (insert/delete/sub sequence) by backtracking.
  • Solve LC 583 (delete-only edit distance) using LCS in 5 min.
  • Explain why three transitions suffice.

10. Company Context

  • Google: L5/L6. Bar Raiser favorite; expects edit-script reconstruction.
  • Apple: Siri / autocorrect teams; Damerau variant relevant.
  • Meta: E5 onsite; LC 583 follow-up.
  • Amazon: L6+; productized as “fuzzy match for search query.”
  • Microsoft: Office spellcheck team; expects Damerau and Hirschberg awareness.

Scorecard for strong: “Solved O(m·n), articulated three transitions cleanly, mentioned Damerau and Hirschberg, related to LCS, reconstructed edit script when asked.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
Base casesWrong (zeros)Correct+ explains+ derived from definition
Three transitionsMisses oneMemorizedJustifies each+ connects to insert/delete bijection
Space compressionO(m·n)+ with prompt1D with prev_diag+ Hirschberg O(min(m,n)) + reconstruction
VariantsDoesn’t knowNames LevenshteinDamerau+ Gotoh affine + BLOSUM + Needleman-Wunsch

12. Level Delta

  • Mid (L4): Correct O(m·n), correct base cases, correct three transitions.
  • Senior (L5): + 1D space + reconstructs edit script + Damerau variant.
  • Staff (L6): + Hirschberg for memory-bounded reconstruction + LCS↔edit-distance relationship + affine gap costs (Gotoh).
  • Principal (L7+): + BLOSUM scoring matrices in production bioinformatics + Smith-Waterman local alignment + Myers’s O((m+n)·D) diff algorithm + parallelization (anti-diagonal wavefront).

13. Follow-up Q&A

Q1: Print the actual edit script. A1: Backtrack from dp[m][n] choosing whichever transition realized the min, emit op (match/sub/insert/delete) at each step, reverse.

Q2: Costs differ per operation type (insert=1, delete=2, sub=3). A2: Replace the constants in the min: dp[i][j] = min(dp[i-1][j-1] + cost_sub, dp[i-1][j] + cost_del, dp[i][j-1] + cost_ins).

Q3: Damerau-Levenshtein (adjacent swaps allowed). A3: Add dp[i-2][j-2] + 1 when i,j ≥ 2, word1[i-1]==word2[j-2], word1[i-2]==word2[j-1]. Captures transpositions like “teh”↔“the”.

Q4: Memory-bounded for million-character strings. A4: Hirschberg’s algorithm — divide-and-conquer using O(min(m,n)) space and O(m·n) time; reconstructs full alignment.

Q5: When substitution costs more than insert+delete, what happens? A5: The DP still works (still picks the cheaper combo), but you can equivalently drop the substitute transition; result equals m + n - 2·lcs(word1, word2) (insert/delete-only edit distance).

14. Solution Walkthrough

See solution.py:

  • min_distance_2d — O(m·n) DP, full table.
  • min_distance_1d — O(min(m,n)) space with prev_diag trick.
  • min_distance_reconstruct — returns the edit script (list of (op, char) tuples).
  • min_distance_brute — uncached recursion (exponential, n ≤ 7 in stress).

15. Beyond the Problem

Principal code review: “Edit Distance is the spine of every fuzzy-matching system on Earth: spell-check, autocorrect, DNA alignment, plagiarism detection, OCR post-processing. The naive DP you wrote scales to ~10⁶ × 10⁶ in CPU time but not in memory — and the moment you need to align two human genomes you’ll meet Hirschberg, Gotoh, Myers, and Hunt-Szymanski. Real bioinformatics tools (BWA, Bowtie2) further specialize: they index references with FM-index and use seed-and-extend rather than full DP. The interview question asks ‘what’s the distance’ — production asks ‘what’s the alignment, what’s the score under BLOSUM62, can we afford it at scale, can we do it on a GPU.’ Memorize the recurrence; learn the ecosystem.”