On this page
Description
How different are two strings? "Did you mean...?" suggestions, fuzzy search and DNA alignment all need a number for that: the fewest single-character insertions, deletions and replacements that turn one string into the other. This is the Levenshtein distance. Trying every edit sequence is hopeless. The same two-prefix state as LCS turns it into a table fill with three moves per cell.
We'll go from simple to more technical:
- The pattern: dp[i][j] from the diagonal (replace or match), above (delete) and left (insert).
- A second flavor: operations with different costs.
- Where edit distance runs in production (spell check, fuzzy search, record matching).
- What breaks it: base cases, a missing move, and unscaled costs.
The approach
Java
int minDistance(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1]; // dp[i][j] = edits to turn a[0..i) into b[0..j)
for (int i = 0; i <= m; i++) dp[i][0] = i; // delete all i characters
for (int j = 0; j <= n; j++) dp[0][j] = j; // insert all j characters
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // match: no edit needed
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], // replace a's char with b's
Math.min(dp[i - 1][j], // delete a's char
dp[i][j - 1])); // insert b's char
}
}
}
return dp[m][n];
}
Python
def min_distance(a: str, b: str) -> int:
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)] # dp[i][j] = edits to turn a[:i] into b[:j]
for i in range(m + 1):
dp[i][0] = i # delete all i characters
for j in range(n + 1):
dp[0][j] = j # insert all j characters
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # match: no edit needed
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1], # replace a's char with b's
dp[i - 1][j], # delete a's char
dp[i][j - 1]) # insert b's char
return dp[m][n]
Look at the last characters. If they match, nothing needs to happen to them. If not, the last edit either replaced a's last character (diagonal), deleted it (from above), or inserted b's last character (from the left) - take the cheapest. The base row and column are the only way to turn something into an empty string (all deletes) or build from nothing (all inserts). "robot" to "boat" is 3; "kitten" to "sitting" is 3.
A second flavor: operations with different costs
Real systems often weigh operations differently - a replacement might cost more than a delete-plus-insert, or insertions might be cheap. The recurrence doesn't change shape; each move just carries its own cost, and so do the base cases:
Java
for (int i = 1; i <= m; i++) dp[i][0] = i * deleteCost;
for (int j = 1; j <= n; j++) dp[0][j] = j * insertCost;
// cell: min(dp[i-1][j-1] + (match ? 0 : replaceCost), dp[i-1][j] + deleteCost, dp[i][j-1] + insertCost)
Python
for i in range(1, m + 1):
dp[i][0] = i * delete_cost
for j in range(1, n + 1):
dp[0][j] = j * insert_cost
# cell: min(dp[i-1][j-1] + (0 if match else replace_cost), dp[i-1][j] + delete_cost, dp[i][j-1] + insert_cost)
With insert = delete = 1 and replace = 5, "abc" to "adc" costs 2 (delete b, insert d) rather than 5 - the DP finds that automatically. Forgetting to scale the base cases (writing dp[i][0] = i) is the classic slip. With only insertions and deletions allowed, the distance is m + n - 2 * LCS.
Where you'll see it
Spell-checkers rank suggestions by edit distance, search engines match queries with typos, record-linkage systems match names across databases ("Jon Smyth" vs "John Smith"), and genome aligners score alignments with weighted versions of this exact table (substitution matrices and gap penalties).
Which tool for which job?
| You need | Use |
|---|---|
| The distance | two-row DP, O(m × n) time |
| Is it at most k? | a band of width 2k + 1 around the diagonal |
| The actual edits | the full table, traced back |
| Typos that swap two letters | Damerau-Levenshtein (adds a transposition move) |
| Nearest words in a dictionary | a BK-tree, or a trie walked with a DP row |
| Insert and delete only | m + n - 2 × LCS |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Row and column 0 left at 0 | "abc" to "" costs nothing | dp[i][0] = i, dp[0][j] = j |
| No replace move | "abc" to "abd" costs 2 instead of 1 | three moves per cell |
| Weighted costs, unweighted base cases | wrong totals | scale the base cases by the delete and insert costs |
| Full table for a yes/no within k | 25,000,000 cells instead of 34,988 | a diagonal band |
| Treating a swap as one edit with plain Levenshtein | "teh" to "the" costs 2 | add the transposition move |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. What do the three neighbors of dp[i][j] represent?
Show answer
dp[i - 1][j - 1]: the last characters are aligned - free if they match, one replace if not. dp[i - 1][j]: a's last character is deleted. dp[i][j - 1]: b's last character is inserted. The cell takes the cheapest.
2. Why is dp[i][0] = i rather than 0?
Show answer
Turning the first i characters of a into an empty string takes exactly i deletions - there's no other way. Leaving it at 0 makes deletions free and understates every distance built on it.
3. With insert = delete = 1 and replace = 5, what does "abc" to "adc" cost?
Show answer
2: delete 'b' and insert 'd' (1 + 1) beats replacing 'b' with 'd' (5). The weighted recurrence compares all three moves at every cell, so it picks the delete-plus-insert route on its own.
Key takeaways
- dp[i][j] = cost to turn a's first i characters into b's first j.
- A match copies the diagonal; otherwise take 1 + the cheapest of replace (diagonal), delete (above) and insert (left).
- Base cases: i deletes down the first column, j inserts along the first row.
- Different operation costs keep the same shape - just weight the moves and the base cases.
- O(m * n) time, O(min(m, n)) space for the distance alone.