Edit distance (Levenshtein)
mediumUp is a deletion, left an insertion, diagonal a replacement - free when the characters match. The traceback turns the number into an actual edit script.
O(m × n)Space O(m × n), or O(min(m,n)) with rolling rowsSaved in this browser - no sign-up, nothing sent anywhere.
How edit distance (levenshtein) works
dp[i][j] is the fewest edits that turn the first i characters of the source into the first j of the target. Three neighbours supply the three operations: the cell above is a deletion, the cell to the left an insertion, the diagonal a replacement. Each costs 1 - except a diagonal step between equal characters, which carries through free. Every cell is one min over three numbers.
The base cases are the trivial conversions: dp[i][0] = i, because turning a prefix into the empty string deletes every character, and dp[0][j] = j, because building from nothing inserts every one. Those two seeded lines are enough - the recurrence grows the rest, and each of the (m + 1) × (n + 1) cells is computed exactly once, where the naive recursion would branch three ways at every character.
The classic example is kitten to sitting: distance 3, via replace k with s, replace e with i, insert g. The number alone rarely suffices - a spell checker needs the operations. Recording which neighbour won each min and walking back from the corner produces exactly that edit script, which is what the visualizer prints in its final step.
Step by step
- Convert kitten to sitting. Column 0 counts deletions 0 through 6; row 0 counts insertions 0 through 7.
- dp[1][1] compares k with s: a mismatch. Delete costs 2, insert costs 2, replace costs 1 - replace wins.
- The next three characters - i, t, t - match in both words, so the 1 rides the diagonal unchanged for three cells.
- Then e meets i: a second mismatch, and another replacement brings the running cost to 2. The n against n carries 2 diagonally again.
- sitting has one character left over. The final g is an insertion, and the corner settles at dp[6][7] = 3.
- Traceback from the corner reads the winners in reverse: insert g, replace e with i, replace k with s - the three edits, back to front.
Complexity
| Worst case time | O(m × n) |
|---|---|
| Space | O(m × n), or O(min(m,n)) with rolling rows |
Reference implementation
Python
def edit_distance(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i # delete everything
for j in range(n + 1): dp[0][j] = j # insert everything
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] # no edit needed
else:
dp[i][j] = 1 + min(dp[i - 1][j], # delete a[i-1]
dp[i][j - 1], # insert b[j-1]
dp[i - 1][j - 1]) # replace
return dp[m][n]JavaScript
function editDistance(a, b) {
const m = a.length, n = b.length;
const dp = Array.from({ length: m + 1 }, (_, i) =>
Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
);
for (let i = 1; i <= m; i++)
for (let j = 1; j <= n; j++)
dp[i][j] = a[i - 1] === b[j - 1]
? dp[i - 1][j - 1]
: 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
return dp[m][n];
}Worth noticing
Three neighbours, three edits
Up is a deletion, left is an insertion, diagonal is a replacement. Each costs one, except a diagonal step between equal characters, which is free. The whole algorithm is that mapping.
The base row and column are the trivial cases
Turning a string into the empty string costs one deletion per character; building it from nothing costs one insertion per character. Those two lines seed everything else.
The traceback tells you *which* edits
The distance alone is rarely enough - spell checkers and diff tools need the operation list. Walking back from the corner and recording which neighbour was chosen produces exactly that script.
kitten → sitting is 3, and always has been
Replace k with s, replace e with i, insert g. This is Levenshtein's own example, and it is the standard sanity check for any implementation.
Common pitfalls
- Zero-filling the first row and column. They must count i deletions and j insertions - left at 0, converting to the empty string looks free.
- Charging for a diagonal step between equal characters. A match costs nothing; adding 1 anyway inflates every distance that passes through it.
- Mixing up insert and delete. With the source on the rows, moving up deletes a source character and moving left inserts a target one - flip the orientation and the labels flip.
- Comparing a[i] with b[j] instead of a[i-1] with b[j-1]. The empty-prefix row shifts the whole table one place off the strings.
- Using the rolling-row space optimisation when the edit script is needed. It keeps the distance but loses the path the traceback follows.
Where it is used
- Spell checkers - candidate corrections are dictionary words within distance 1 or 2 of the typo.
- Fuzzy search and record deduplication, matching names and addresses that differ by a few keystrokes.
- Bioinformatics sequence alignment, where the same table runs with substitution-specific scores.
- LeetCode 72, a standard hard-tier interview question - and the template for a dozen two-string DP variants.
Frequently asked questions
What is the time and space complexity of edit distance?
Time is O(m × n) for strings of length m and n - one constant-time min per cell. Space is O(m × n) for the full table, or O(min(m,n)) with rolling rows when only the distance matters, since each cell reads nothing older than the previous row.
What are the three operations in Levenshtein distance?
Insert a character, delete a character, or replace one with another, each costing 1. In the table they map to the left, upper and diagonal neighbours respectively. A diagonal step between equal characters is the fourth possibility: no edit at all, cost 0.
What is the edit distance between kitten and sitting?
Three: replace k with s, replace e with i, insert g at the end. This is Levenshtein's own example and the standard sanity check - an implementation reporting anything but 3 usually has broken base cases or a missing free-match rule.
Can edit distance be computed faster than O(m × n)?
Not substantially, as far as anyone knows - a strongly subquadratic algorithm would contradict the strong exponential time hypothesis. When the distance is known to be small, though, banded variants that fill only a diagonal strip proportional to that distance run far faster in practice.