Edit Distance (LeetCode 72)
You have two strings, word1 and word2, and three single-character edits at your disposal: insert one, delete one, or replace one.
Work out the fewest such edits needed to transform word1 into word2.
Worked Examples
word1 = "horse", word2 = "ros"3word1 = "intention", word2 = "execution"5⚖️Formal Constraints & Bounds
0 <= word1.length, word2.length <= 500word1andword2consist of lowercase English letters.
Core Insight
2D matrix evaluates all three edit operations simultaneously to guarantee global minimal edit distance.
Real-World Scenario & Production Applications
Spell checker auto-correction, DNA string sequence alignment.
Subproblems & Recurrence Decomposition3 Phases
Converting an empty string to a prefix of length j requires j insertions (dp[0][j] = j). Converting a prefix of length i to an empty string requires i deletions (dp[i][0] = i).
# Base row & column:
for i in range(M + 1): dp[i][0] = i # Deletions
for j in range(N + 1): dp[0][j] = j # InsertionsStep-by-Step Execution Trace Table
| Char Pair | Action | dp Cell Value |
|---|---|---|
| ('h', 'r') | Replace 'h' -> 'r' | 1 |
| ('o', 'o') | Match! inherit diagonal | 1 |
| ('r', 's') | Replace/Delete | 2 |
| Final (5, 3) | Total minimal operations | 3 |
| 1 | dp = [[0] * (n + 1) for _ in range(m + 1)] |
| 2 | for i in range(m + 1): |
| 3 | dp[i][0] = i |
| 4 | for j in range(n + 1): |
| 5 | dp[0][j] = j |
| 6 | for i in range(1, m + 1): |
| 7 | for j in range(1, n + 1): |
| 8 | if word1[i-1] == word2[j-1]: |
| 9 | dp[i][j] = dp[i-1][j-1] |
| 10 | else: |
| 11 | dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) |
| 12 | return dp[m][n] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Edit Distance measures the minimum operations (insert, delete, replace) to transform $word_1$ into $word_2$. At matrix cell $(i, j)$, if characters match, cost is free ($dp[i-1][j-1]$). If they differ, we take $1 + \min(\text{insert: } dp[i][j-1], \text{delete: } dp[i-1][j], \text{replace: } dp[i-1][j-1])$. Initializing boundary rows to prefix deletion and insertion costs guarantees exact Levenshtein distance in $O(M \times N)$ time. ✏️ The Analogy: Proofreading Two Drafts Into Alignment
Imagine transforming one draft of a document into another, one character at a time, tracking your progress in a grid where cell (i, j) means "cost to turn the first i letters of word1 into the first j letters of word2." If the current letters already match, no edit is needed here at all — inherit the cost from before either letter was considered. If they don't match, you have exactly three moves available, and you take whichever is cheapest: delete a letter from word1 (move up a row), insert a letter to match word2 (move left a column), or replace the letter outright (move diagonally) — each costing one edit on top of the smaller sub-problem's already-known cost.
🔑 The Key Idea in the Code
Each of the three directions in the grid corresponds to exactly one edit operation — up is delete, left is insert, diagonal is replace — so the minimum edit distance is really the cheapest path through this grid from corner to corner.
Mismatch branch cost omission: Writing
min(insert, delete, replace)without adding to the mismatch transition:dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).Match branch cost inflation: Adding when characters match (
word1[i-1] == word2[j-1]). Matching characters cost 0 operations; the transition must inherit the diagonal directly:dp[i][j] = dp[i-1][j-1].Base case non-zero initialization: Failing to initialize
dp[i][0] = i(deleting all chars) anddp[0][j] = j(inserting all chars). Leaving base rows as zero corrupts the entire alignment calculation.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Minimum transformation steps between two strings using insertions, deletions, replacements.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: dp[i][j] stores the edit distance between word1[:i] and word2[:j].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Off-by-one indexing between 1-indexed DP table and 0-indexed string characters.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I allocate an
(m+1) x (n+1)DP table and initialize border distancesdp[i][0] = ianddp[0][j] = j. For each pair(i, j), ifword1[i-1] == word2[j-1],dp[i][j] = dp[i-1][j-1]. Otherwise,dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). Runs in O(M · N) time and O(M · N) space."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: 2D DP table for word1 of length M and word2 of length N. If characters match, take diagonal; else 1 + min(insert, delete, replace). Rolling row optimization reduces space to O(min(M, N)).
O(min(M, N)) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Two rows of size min(M, N) + 1.
T(M, N) = M · N = O(M · N)
Derivation Progression
1 + min(insert, delete, replace)
Evaluates all 3 edit operations in O(1) per cell.
if w1[i-1] == w2[j-1]: dp[i][j] = dp[i-1][j-1]
Free advance when characters match.
O(min(M, N)) row buffers
Retains only active and previous row.
Variable Definitions
Length of source string word1
Length of target string word2
Memory Architecture & Bounds
O(1) Iterative
O(min(M, N)) 1D rolling array
O(1) Min edits integer
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum operations to convert word1 to word2", "insert, delete, replace". Levenshtein Distance Matrix: - If characters match: (free). - Else: .
. Time budget runs in ms.
Off-by-one in 1-indexed array: and .
Edit Distance (LeetCode 72)
You have two strings, word1 and word2, and three single-character edits at your disposal: insert one, delete one, or replace one.
Work out the fewest such edits needed to transform word1 into word2.
Worked Examples
word1 = "horse", word2 = "ros"3word1 = "intention", word2 = "execution"5⚖️Formal Constraints & Bounds
0 <= word1.length, word2.length <= 500word1andword2consist of lowercase English letters.
Core Insight
2D matrix evaluates all three edit operations simultaneously to guarantee global minimal edit distance.
Real-World Scenario & Production Applications
Spell checker auto-correction, DNA string sequence alignment.
Subproblems & Recurrence Decomposition3 Phases
Converting an empty string to a prefix of length j requires j insertions (dp[0][j] = j). Converting a prefix of length i to an empty string requires i deletions (dp[i][0] = i).
# Base row & column:
for i in range(M + 1): dp[i][0] = i # Deletions
for j in range(N + 1): dp[0][j] = j # InsertionsStep-by-Step Execution Trace Table
| Char Pair | Action | dp Cell Value |
|---|---|---|
| ('h', 'r') | Replace 'h' -> 'r' | 1 |
| ('o', 'o') | Match! inherit diagonal | 1 |
| ('r', 's') | Replace/Delete | 2 |
| Final (5, 3) | Total minimal operations | 3 |
| 1 | dp = [[0] * (n + 1) for _ in range(m + 1)] |
| 2 | for i in range(m + 1): |
| 3 | dp[i][0] = i |
| 4 | for j in range(n + 1): |
| 5 | dp[0][j] = j |
| 6 | for i in range(1, m + 1): |
| 7 | for j in range(1, n + 1): |
| 8 | if word1[i-1] == word2[j-1]: |
| 9 | dp[i][j] = dp[i-1][j-1] |
| 10 | else: |
| 11 | dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) |
| 12 | return dp[m][n] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Edit Distance measures the minimum operations (insert, delete, replace) to transform $word_1$ into $word_2$. At matrix cell $(i, j)$, if characters match, cost is free ($dp[i-1][j-1]$). If they differ, we take $1 + \min(\text{insert: } dp[i][j-1], \text{delete: } dp[i-1][j], \text{replace: } dp[i-1][j-1])$. Initializing boundary rows to prefix deletion and insertion costs guarantees exact Levenshtein distance in $O(M \times N)$ time. ✏️ The Analogy: Proofreading Two Drafts Into Alignment
Imagine transforming one draft of a document into another, one character at a time, tracking your progress in a grid where cell (i, j) means "cost to turn the first i letters of word1 into the first j letters of word2." If the current letters already match, no edit is needed here at all — inherit the cost from before either letter was considered. If they don't match, you have exactly three moves available, and you take whichever is cheapest: delete a letter from word1 (move up a row), insert a letter to match word2 (move left a column), or replace the letter outright (move diagonally) — each costing one edit on top of the smaller sub-problem's already-known cost.
🔑 The Key Idea in the Code
Each of the three directions in the grid corresponds to exactly one edit operation — up is delete, left is insert, diagonal is replace — so the minimum edit distance is really the cheapest path through this grid from corner to corner.
Mismatch branch cost omission: Writing
min(insert, delete, replace)without adding to the mismatch transition:dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).Match branch cost inflation: Adding when characters match (
word1[i-1] == word2[j-1]). Matching characters cost 0 operations; the transition must inherit the diagonal directly:dp[i][j] = dp[i-1][j-1].Base case non-zero initialization: Failing to initialize
dp[i][0] = i(deleting all chars) anddp[0][j] = j(inserting all chars). Leaving base rows as zero corrupts the entire alignment calculation.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Minimum transformation steps between two strings using insertions, deletions, replacements.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: dp[i][j] stores the edit distance between word1[:i] and word2[:j].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Off-by-one indexing between 1-indexed DP table and 0-indexed string characters.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I allocate an
(m+1) x (n+1)DP table and initialize border distancesdp[i][0] = ianddp[0][j] = j. For each pair(i, j), ifword1[i-1] == word2[j-1],dp[i][j] = dp[i-1][j-1]. Otherwise,dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). Runs in O(M · N) time and O(M · N) space."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: 2D DP table for word1 of length M and word2 of length N. If characters match, take diagonal; else 1 + min(insert, delete, replace). Rolling row optimization reduces space to O(min(M, N)).
O(min(M, N)) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Two rows of size min(M, N) + 1.
T(M, N) = M · N = O(M · N)
Derivation Progression
1 + min(insert, delete, replace)
Evaluates all 3 edit operations in O(1) per cell.
if w1[i-1] == w2[j-1]: dp[i][j] = dp[i-1][j-1]
Free advance when characters match.
O(min(M, N)) row buffers
Retains only active and previous row.
Variable Definitions
Length of source string word1
Length of target string word2
Memory Architecture & Bounds
O(1) Iterative
O(min(M, N)) 1D rolling array
O(1) Min edits integer
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum operations to convert word1 to word2", "insert, delete, replace". Levenshtein Distance Matrix: - If characters match: (free). - Else: .
. Time budget runs in ms.
Off-by-one in 1-indexed array: and .