Edit Distance
Problem Statement
Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2. The allowed operations are insert a character, delete a character, or replace a character.
Input
Two lowercase strings word1 and word2.
Output
An integer: the minimum number of insert, delete, and replace operations needed to convert word1 into word2.
Constraints
- •
0 <= word1.length, word2.length <= 500 - •
word1 and word2 consist of lowercase English letters
Examples
Example 1
word1 = horse, word2 = ros
3Example 2
word1 = intention, word2 = execution
5Example 3
word1 = empty string, word2 = abc
3Learning Objectives
- Model edit operations as transitions between prefixes of two strings.
- Set empty-prefix base cases for converting to or from an empty string.
- Map insert, delete, and replace to the correct neighbouring DP cells.
- Recognise edit distance as a minimization version of two-sequence DP.
Intuition
Again use prefixes, but now the cell is a cost rather than a length. Suppose you want to convert the first i characters of word1 into the first j characters of word2.
If the two last characters already match, they can stay as they are. The cost is whatever it took to convert the smaller prefixes before them.
If they differ, the final operation in an optimal solution must be one of three choices. Insert the last character of word2, delete the last character of word1, or replace the last character of word1. Each choice reduces the problem to a neighbouring prefix cell plus one operation. Taking the minimum gives the optimal edit count.
Common mistakes
- ×Forgetting that empty strings are valid inputs, so the first row and first column are essential.
- ×Swapping the meaning of insert and delete transitions. The formula can still work, but the explanation becomes inconsistent.
- ×Adding one operation even when the current characters already match.
- ×Using a greedy local replacement whenever characters differ, which misses cases where insert or delete is cheaper.
- ×Returning **dp[m - 1][n - 1]** from a table built with extra prefix rows and columns.
State Definition
Let dp[i][j] be the minimum number of edits needed to convert the first i characters of word1 into the first j characters of word2. The answer is dp[m][n].
State Transition
Base cases describe conversion involving an empty prefix:
dp[i][0] = i because converting a non-empty prefix to empty requires deleting all i characters.
dp[0][j] = j because converting empty to a prefix of length j requires inserting all j characters.
For i > 0 and j > 0, if word1[i - 1] == word2[j - 1], then dp[i][j] = dp[i - 1][j - 1].
Otherwise:
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
Those three neighbours represent insert, delete, and replace respectively.
Solutions
Solution: 2D edit-cost tabulation
Use this as the standard solution. It is concise, handles empty strings cleanly, and makes each edit operation visible in the recurrence.
Build a prefix table from smaller prefixes to larger prefixes. The first row and column are direct costs against the empty string. Every other cell either copies the diagonal on a character match or takes one plus the minimum of the insert, delete, and replace predecessor cells.
Step-by-step
- Let m and n be the input lengths.
- Allocate dp[m + 1][n + 1].
- Fill dp[i][0] = i and dp[0][j] = j for the empty-prefix conversions.
- For each pair of non-empty prefixes, compare word1.charAt(i - 1) and word2.charAt(j - 1).
- Copy the diagonal if they match; otherwise compute one plus the minimum insert, delete, or replace cost.
- Return dp[m][n].
O(m · n)
O(m · n)
The table contains one state for every pair of prefix lengths.
Java implementation
Dry Run
Sample input
word1 = horse, word2 = ros. Each row is the DP row against prefixes of ros, including the empty-prefix column.
| word1 prefix | dp row for prefixes of ros | reason for final cell |
|---|---|---|
| empty | [0,1,2,3] | Insert all target characters |
| h | [1,1,2,3] | Replace h with r, then insert as needed |
| ho | [2,2,1,2] | The o characters match at column 2 |
| hor | [3,2,2,2] | The r can match after deleting earlier extra characters |
| hors | [4,3,3,2] | The s characters match at column 3 |
| horse | [5,4,4,3] | Delete the trailing e after reaching ros |
The bottom-right value is 3, so horse can be converted to ros in three edits.
Complexity Analysis
The full prefix table is O(m · n) time and space. A rolling-row optimization is possible, but the 2D table is clearer and is the expected first interview answer.
2D edit-cost tabulation
O(m · n)
O(m · n)
The table contains one state for every pair of prefix lengths.
Interview Tips
Name the operation represented by each neighbour. dp[i][j - 1] means insert the target character, dp[i - 1][j] means delete the source character, and dp[i - 1][j - 1] means replace. This prevents the recurrence from sounding memorized.
Likely follow-ups
- Can you reduce the memory to O(min(m, n)) while keeping the same recurrence?
- How would the recurrence change if insert, delete, and replace had different costs?
- How would you return the actual edit script, not just its length?
- What if only insertions and deletions are allowed?
Similar Problems
Key Takeaways
- Edit distance is a minimum-cost DP over two prefixes.
- Empty-prefix base cases encode all insertions or all deletions.
- A character match costs nothing and moves diagonally.
- A mismatch chooses the cheapest insert, delete, or replace predecessor plus one.