Edit distance
Why it exists
Problem: Determining the minimum number of edits to transform one string into another naively requires branching on insert, delete, or replace at every character, leading to an exponential O(3^n) time complexity.
Better idea: Use the exact same grid shape as Longest Common Subsequence, but instead of finding common characters, assign a cost to mismatches. At each step, take the minimum cost of the three possible string operations.
Mental model
It's the LCS grid, but you pay a cost of 1 to move up (delete), left (insert), or diagonally (replace) when characters don't match. If they match, moving diagonally is free.
We build a 2D table comparing prefixes. If the characters match, no operation is needed, so we carry over the cost from the prefixes before them. If they mismatch, we find the cheapest path among three choices: replacing the character (diagonal neighbor), deleting a character from the first string (top neighbor), or inserting a character (left neighbor).
Repeated decision: do these two characters match (free, move diagonally) -- if not, which of insert/delete/replace (each costing 1) gives the cheapest path here?
Explanation
Edit Distance (often called Levenshtein Distance) calculates the minimum operations (insert, delete, replace) to turn string `A` into string `B`.
We define our state precisely: `dp[i][j]` is the edit distance between the first `i` characters of `A` and the first `j` characters of `B`.
The recurrence maps directly to operations:
- If `A[i-1] == B[j-1]`, no edit is needed: `dp[i][j] = dp[i-1][j-1]` (a free diagonal move).
- Otherwise, `dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])`.
Here, `dp[i-1][j-1]` represents replacing a character. `dp[i-1][j]` represents deleting a character from `A`. `dp[i][j-1]` represents inserting a character into `A`.
The base cases define the edges: `dp[i][0] = i` because turning an `i`-length string into an empty string takes `i` deletions. `dp[0][j] = j` because turning an empty string into a `j`-length string requires `j` insertions.
Like LCS, this is a 2D DP problem that takes `O(m*n)` time and space. Both top-down memoization and bottom-up tabulation are perfectly valid strategies to compute the final table.
Let's trace `A = "CAT"` to `B = "BAT"`. We build a `4x4` grid. Row 0 is `[0, 1, 2, 3]` (inserting into empty string costs 1,2,3) and Col 0 is `[0, 1, 2, 3]` (deleting to empty string costs 1,2,3).
- **Row C:**
- Col B: Mismatch. `1 + min(diag:0 [replace], left:1 [insert], up:1 [delete])`. Minimum is diag, so `1` (replaced C with B).
- Col A: Mismatch. `1 + min(diag:1 [replace], left:1 [insert], up:2 [delete])`. Minimum is left, so `2` (inserted A).
- Col T: Mismatch. `1 + min(diag:2 [replace], left:2 [insert], up:3 [delete])`. Minimum is left, so `3` (inserted T).
- **Row A:**
- Col B: Mismatch. `1 + min(diag:1 [replace], left:2 [insert], up:1 [delete])`. Minimum is up, so `2` (deleted A).
- Col A: Match! Free diagonal, copy `dp[C][B]` directly. Result: `1`.
- Col T: Mismatch. `1 + min(diag:2, left:1, up:3)`. Minimum is left, so `2` (inserted T).
- **Row T:**
- Col B: Mismatch. `1 + min(diag:2, left:3, up:2)`. Minimum is up, so `3` (deleted T).
- Col A: Mismatch. `1 + min(diag:2, left:3, up:1)`. Minimum is up, so `2` (deleted T).
- Col T: Match! Free diagonal, copy `dp[A][A]` directly. Result: `1`.
The bottom-right cell is 1, meaning it takes 1 operation (replace C with B) to turn CAT into BAT.
Key points
- State Definition: `dp[i][j]` represents the minimum edit operations to transform `A[0..i-1]` into `B[0..j-1]`.
- The Three Operations: Looking up (`i-1`, `j`) is a delete. Looking left (`i`, `j-1`) is an insert. Looking diagonally up-left (`i-1`, `j-1`) is a replace.
- Base Case Initialization: The first row and first column must be initialized to their index values (0, 1, 2, ...), representing the cost of deleting all characters to reach an empty string.
Common mistakes
- Initializing base cases to 0: A common mistake is treating the first row and column as 0 like in LCS. In edit distance, converting a string of length 5 to an empty string costs 5, not 0.
- Mixing up the operations: Failing to correctly map the top, left, and diagonal neighbors to their respective delete, insert, and replace operations makes the grid trace incorrect even if the minimum happens to output the right number.
Recall questions
- What does `dp[i][j]` represent in Edit Distance?
- What are the base cases for the first row and column, and why?
- Which neighbor cell corresponds to the 'replace' operation?
Questions & answers
Given two words, return the minimum number of steps to make them match, where each step can only insert or delete a character (no replacements allowed).
Use the same grid shape but remove the diagonal replacement option from the recurrence. Mismatches only take `1 + min(dp[i-1][j], dp[i][j-1])`.
Approach: Modify the edit distance recurrence to restrict allowed operations.
Calculate string similarity for a spell-checker suggesting corrections.
Run edit distance against a dictionary and return words with the smallest distance.
Approach: Levenshtein distance is the standard metric for typographical similarity.
Continue learning
Previous: Longest common subsequence