Edit Distance
Edit Distance is LeetCode 72 (Hard). You are given two strings, word1 and word2. Return the minimum number of operations that turn word1 into word2.
Each operation changes word1 by one character and costs 1:
- insert a character anywhere;
- delete any character;
- replace any character with a different one.
The smallest possible count is the minimum edit distance between the strings, better known as the Levenshtein distance.
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters.
Intuition
Edit distance, also called the Levenshtein distance, is the fewest single-character inserts, deletes and replaces that turn one string into another. Trying every edit sequence is exponential, but one question makes the problem small: what happened to the last letters?
If the last letters of two prefixes match, they need no edit, and the cost is whatever the shorter prefixes cost. If they differ, the final edit was a replace, a delete or an insert, and each of those leaves a smaller prefix pair to solve. Every optimal edit script ends in one of these cases, so taking the cheapest is exact. The smaller pairs are always solved first, so the edit distance solution fills a table without any recursion.
Two strings, a menu of per-character moves, and a question about the cheapest way to line them up. That is a 2-D prefix DP: edit distance dynamic programming fills one cell per pair of prefixes. Each allowed move becomes one neighbour in the table: diagonal is replace (or free match), up is delete, left is insert. The same grid solves longest common subsequence, with max instead of min and zeros on the edges.
Approach
Before reading on, write down what dp[i][j] should mean, which three cells it reads, and what the first row and column must be. Aim for O(m·n) time.
Define the state over prefixes
Let dp[i][j] be the minimum operations to convert word1[:i] into word2[:j], in a table of (m+1) × (n+1) cells. The extra row and column stand for the empty prefix, which gives the recurrence a place to stop without special-casing index 0.
Fill the base row and column
dp[i][0] = i: turniletters into nothing by deleting all of them.dp[0][j] = j: buildjletters from nothing by inserting all of them.
These are the only cells that do not read a neighbour, and every other value chains back to them.
Apply the recurrence cell by cell
- If
word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]. - Otherwise:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])for replace, delete and insert.
Fill rows top to bottom, left to right, so the up, left and diagonal cells are always ready.
Read the answer, and recover the edits if asked
The answer is dp[m][n]. To list the actual operations, walk back from that corner: move diagonally on a free match, otherwise step to whichever neighbour produced the +1 and record that operation.
Reduce space when only the number is needed
Each row reads only the row above and the cell to its left, so two rows (or one row plus a saved diagonal) are enough: O(n) space. Keep the full table only if you need the traceback.
Edit Distance solution in Python | C++ | Java
dp[i][j] is the cost of turning the first i letters of word1 into the first j of word2. Turning a prefix into the empty string costs one delete per letter, and building a prefix from nothing costs one insert per letter. These edges are not zeros, and every other cell chains back to them.dp[1][1] — 'h' ≠ 'r': 1 + min(replace 0, delete 1, insert 1) = 1. Cheapest move is replace.dp[1][2] — 'h' ≠ 'o': 1 + min(replace 1, delete 2, insert 1) = 2. Cheapest move is replace.dp[1][3] — 'h' ≠ 's': 1 + min(replace 2, delete 3, insert 2) = 3. Cheapest move is replace.dp[2][1] — 'o' ≠ 'r': 1 + min(replace 1, delete 1, insert 2) = 2. Cheapest move is replace.dp[2][2] — 'o' = 'o': the letters already match, so copy the diagonal for free.dp[2][3] — 'o' ≠ 's': 1 + min(replace 2, delete 3, insert 1) = 2. Cheapest move is insert.dp[3][1] — 'r' = 'r': the letters already match, so copy the diagonal for free.dp[3][2] — 'r' ≠ 'o': 1 + min(replace 2, delete 1, insert 2) = 2. Cheapest move is delete.dp[3][3] — 'r' ≠ 's': 1 + min(replace 1, delete 2, insert 2) = 2. Cheapest move is replace.dp[4][1] — 's' ≠ 'r': 1 + min(replace 3, delete 2, insert 4) = 3. Cheapest move is delete.dp[4][2] — 's' ≠ 'o': 1 + min(replace 2, delete 2, insert 3) = 3. Cheapest move is replace.dp[4][3] — 's' = 's': the letters already match, so copy the diagonal for free.dp[5][1] — 'e' ≠ 'r': 1 + min(replace 4, delete 3, insert 5) = 4. Cheapest move is delete.dp[5][2] — 'e' ≠ 'o': 1 + min(replace 3, delete 3, insert 4) = 4. Cheapest move is replace.dp[5][3] — 'e' ≠ 's': 1 + min(replace 3, delete 2, insert 4) = 3. Cheapest move is delete.dp[i][j] is the cost of turning the first i letters of word1 into the first j of word2. Turning a prefix into the empty string costs one delete per letter, and building a prefix from nothing costs one insert per letter. These edges are not zeros, and every other cell chains back to them.dp[1][1] — 'c' = 'c': the letters already match, so copy the diagonal for free.dp[1][2] — 'c' ≠ 'u': 1 + min(replace 1, delete 2, insert 0) = 1. Cheapest move is insert.dp[1][3] — 'c' ≠ 't': 1 + min(replace 2, delete 3, insert 1) = 2. Cheapest move is insert.dp[2][1] — 'a' ≠ 'c': 1 + min(replace 1, delete 0, insert 2) = 1. Cheapest move is delete.dp[2][2] — 'a' ≠ 'u': 1 + min(replace 0, delete 1, insert 1) = 1. Cheapest move is replace.dp[2][3] — 'a' ≠ 't': 1 + min(replace 1, delete 2, insert 1) = 2. Cheapest move is replace.dp[3][1] — 't' ≠ 'c': 1 + min(replace 2, delete 1, insert 3) = 2. Cheapest move is delete.dp[3][2] — 't' ≠ 'u': 1 + min(replace 1, delete 1, insert 2) = 2. Cheapest move is replace.dp[3][3] — 't' = 't': the letters already match, so copy the diagonal for free.dp[i][j] is the cost of turning the first i letters of word1 into the first j of word2. Turning a prefix into the empty string costs one delete per letter, and building a prefix from nothing costs one insert per letter. These edges are not zeros, and every other cell chains back to them.Common pitfalls
Leaving the first row and column at zero
dp = [[0] * (n + 1) for _ in range(m + 1)] # straight into the double loop
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = jTurning "abc" into "" costs 3 deletions, not 0. LCS starts from zeros, edit distance does not; copying the LCS template makes every distance too small.
Adding 1 when the letters match
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]A match needs no operation. In LCS a match is the only time the value grows, so this is the habit that carries over wrongly.
Forgetting the diagonal on a mismatch
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
Without the diagonal there is no replace, so one substitution is billed as a delete plus an insert. "cat" to "cut" then returns 2 instead of 1.
Edge cases
Return the other string's length. No special branch is needed: the loops do not run and the answer is the base row or column value.
Complexity
Edit distance vs related string DPs
The same prefix grid solves several problems. What changes is the menu of moves and the base cases.
| Problem | Allowed moves | Base cases | Cell rule |
|---|---|---|---|
| Edit Distance (72) | insert, delete, replace | dp[i][0]=i, dp[0][j]=j | match: diagonal; else 1 + min of 3 |
| Longest Common Subsequence (1143) | keep a matching pair | all zeros | match: diagonal +1; else max of up, left |
| Delete Operation for Two Strings (583) | delete from either string | dp[i][0]=i, dp[0][j]=j | match: diagonal; else 1 + min of up, left |
| One Edit Distance (161) | exactly one edit | none needed | linear scan, no table |
Edit Distance FAQ
What is edit distance?
Edit distance (Levenshtein distance) is the minimum number of single-character insertions, deletions and replacements needed to turn one string into another. For example, horse becomes ros in 3 edits: replace h with r, delete r, delete e.
What are the steps of the edit distance algorithm?
- State:
dp[i][j]= minimum edits to turn the firsticharacters of word1 into the firstjcharacters of word2. - Base cases:
dp[i][0] = i(delete all),dp[0][j] = j(insert all). - Recurrence: if
word1[i-1] == word2[j-1],dp[i][j] = dp[i-1][j-1]; otherwisedp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])for replace, delete, insert. - Order: fill row by row; the answer is
dp[m][n]. - Complexity: O(m·n) time, O(m·n) space, reducible to O(n).
- Example: horse to ros gives 3.
Why is edit distance solved with dynamic programming?
The cost for two full strings depends only on the costs for shorter prefixes (optimal substructure), and the same prefix pairs come up again and again in a brute-force search (overlapping subproblems). A table computes each of the (m+1)(n+1) prefix pairs once.
How do you find which operations were used?
Keep the full table and walk back from dp[m][n]. On a match move diagonally with no edit; otherwise move to the neighbour whose value is exactly one less and record that operation: diagonal is replace, up is delete, left is insert.
What is the difference between edit distance and LCS?
LCS maximises the number of kept matching characters and allows no replace. Edit distance minimises the number of changes and allows replace. If only insert and delete are allowed, the distance equals m + n - 2 × LCS.