The site's second dynamic programming entry,
and a direct generalization of the first. Longest Common Subsequence asks how much of two strings already
lines up if all you're allowed to do is skip characters. Edit distance (also called Levenshtein distance)
asks a sharper question: what's the fewest single-character edits — insert, delete, or substitute —
needed to turn one string into the other? "kitten" becomes "sitting" in exactly three edits: substitute
k→s, substitute e→i, insert g at the end.
No two-edit sequence manages it — that's the number this page's table computes and then proves, by
reconstructing the actual edit script.
Two fixed strings, A = "kitten" and B = "sitting" — the standard textbook pair.
Press Step or Run to watch the table fill in: each cell dp[i][j]
holds the edit distance between the first i characters of A and the first
j characters of B. Once the table is full, the demo backtracks from the
bottom-right corner, recovering the actual sequence of edits — watch the highlighted path, then the
alignment strip below once it's done.
Switch the mode dropdown to space-optimized to see the two-row trick from Pitfalls
run for real: instead of a full (m+1)×(n+1) table, only a prev row and a
curr row ever exist at once — with one extra wrinkle this page's recurrence needs that
Longest Common Subsequence's didn't: curr[0] has to be set to i by hand
before the inner loop starts, the rolling equivalent of this page's base column. The stats line
tracks exactly how many cells that saves. The trade is real too — this mode reports the edit
distance only, never the edit script itself, because once a row is overwritten there's
nothing left to backtrack through.
Switch it to top-down (memoized recursion) to see the other fix Pitfalls names: the
same recurrence, called as ordinary recursion starting from dp[m][n], with each answer
cached in a map keyed by (i, j) the first time it's computed. Unfilled cells show as
· until the recursion actually reaches them — this mode still reconstructs the full edit
script (the memo is a complete substitute for the table), but computes strictly fewer cells than the
version above, though — as Pitfalls checks honestly — not nearly as few as Longest Common Subsequence's
own top-down mode saves on a table the same size.
The base cases come first: turning i characters into nothing takes i deletes,
so dp[i][0] = i; turning nothing into j characters takes j inserts, so
dp[0][j] = j. That's the table's top row and left column, filled before any real comparison
happens — it's why the table here needs a base row and column of actual counts, not the
all-zero border Longest Common Subsequence's table had (there, an empty prefix trivially shares nothing
with anything; here, an empty prefix still costs something to reach).
From there, each cell has two cases. If the two current characters already match —
A[i-1] === B[j-1] — no edit is needed for this position at all: dp[i][j] = dp[i-1][j-1],
exactly what it cost to align everything before this matching pair. If they don't match, one of three edits
has to happen, and the recurrence tries all three and keeps the cheapest: substitute
A[i-1] for B[j-1] (dp[i-1][j-1] + 1), delete
A[i-1] (dp[i-1][j] + 1), or insert B[j-1]
(dp[i][j-1] + 1). Each option reduces the problem to one already-solved smaller one plus one
guaranteed edit, so dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) — the same
optimal-substructure and overlapping-subproblems argument
Longest Common Subsequence's Why it
works section makes, just with three predecessor cells to compare instead of two.
Builds the table bottom-up, then walks it backward from the last cell to recover the actual edit script — not just the count:
function editDistance(a, b) {
const m = a.length, n = b.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i <= m; i++) dp[i][0] = i; // delete all i characters
for (let j = 0; j <= n; j++) dp[0][j] = j; // insert all j characters
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
}
}
}
// backtrack from the bottom-right corner to recover the edits, not just the count
let i = m, j = n;
const ops = [];
while (i > 0 || j > 0) {
if (i > 0 && j > 0 && a[i - 1] === b[j - 1] && dp[i][j] === dp[i - 1][j - 1]) {
ops.push({ op: 'match', ch: a[i - 1] });
i--; j--;
} else if (i > 0 && j > 0 && dp[i][j] === dp[i - 1][j - 1] + 1) {
ops.push({ op: 'sub', from: a[i - 1], to: b[j - 1] });
i--; j--;
} else if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {
ops.push({ op: 'del', ch: a[i - 1] });
i--;
} else {
ops.push({ op: 'ins', ch: b[j - 1] });
j--;
}
}
ops.reverse();
return { distance: dp[m][n], ops };
}Longest Common Subsequence is edit distance with only two of the three edits allowed, each
still costing one. Restrict this page's recurrence to insert and delete only — no substitute —
and minimizing edits to transform A into B becomes exactly "maximize the shared
subsequence, delete everything else from A, insert everything else from B."
That's not a coincidence worth glossing over: it's the same table, the same backtracking shape, and the
same O(m·n) cost, just with a narrower edit set and a different objective (maximize matches
vs. minimize edits) that happen to be two views of the same underlying subproblem structure.
Ties in the three-way min are broken by an arbitrary priority, not a rule the
problem forces. This page's backtrack step always checks substitute before delete before insert
when more than one option is equally cheap — the same kind of arbitrary tie-break
Longest Common Subsequence's Pitfalls
section already flagged for its own two-way tie. The distance is never ambiguous, but a
version that checked delete or insert first would recover a different (equally short) edit script for
the same pair of strings.
This table costs real memory, and — same as Longest Common Subsequence — there's a cheaper
option if only the distance is needed. Computing dp[i][j] only ever reads row
i-1 and the current row i, so the full O(m·n) table can be trimmed
to two rows, dropping space to O(min(m, n)). The catch is identical too: recovering the actual
edit script, the way this page's demo does, needs the full table to walk back through. Try it live above by
switching to space-optimized mode: on this page's own 6×7 example, that's 16 cells
kept at any moment instead of 56 for the full table, the same saving
Longest Common Subsequence's own
space-optimized mode demonstrates on the identical-sized table.
Top-down memoization saves less here than it does for Longest Common Subsequence — and the
reason is the extra edit this page's recurrence allows. LCS's mismatch case only ever recurses
into two neighbors (up, left); this page's mismatch case recurses into three (substitute's diagonal,
delete's up, insert's left), so a lot more of the table ends up genuinely needed regardless of where the
recursion starts. On this page's own "kitten"/"sitting" example, top-down
computes 50 of the 56 possible cells (48 of those are cache hits) — nowhere near
Longest Common Subsequence's own 32-of-56
saving on a table the same size, because most cells here are mismatches that still need all three
neighbors. The saving does show up where it's structurally possible: two identical 6-character strings
(checked separately, not shown in the demo above) recurse along a single diagonal of matches and touch
just 7 of 49 cells, since a match short-circuits straight past the other two neighbors a
mismatch would need — the same short-circuit LCS's own Pitfalls names, just triggered less often here
because a plain mismatch, not only a non-match and a non-diagonal move, is what forces the
extra branches.
Time: O(m·n) — one constant-time three-way comparison per cell,
(m+1)(n+1) cells total. Space: O(m·n) for the full table (needed
to reconstruct the edit script), or O(min(m, n)) if only the distance is needed — see
Pitfalls above.
Edit distance shows up anywhere "how similar are these two strings" needs a real number instead of a
guess: spell checkers ranking correction candidates, DNA sequence alignment, fuzzy string matching, and
diff-style tools that assign a substitution cost instead of only recognizing exact matches
(plain diff, as Longest Common Subsequence's own Complexity section notes, uses just insert
and delete). For a dynamic-programming table shaped by something other than two strings, see the
0/1 knapsack problem — items and a capacity instead of string
prefixes, same underlying idea. This same recurrence also has a bit-parallel form: see
Bitap with Edit Distance (Wu–Manber), which packs
one row of this exact table into a machine word (changing one base case along the way, to search a
pattern inside a longer text instead of comparing two whole strings) and updates it with a handful
of shifts instead of walking the grid cell by cell. For a version that keeps the table shape but
restricts which cells get filled, see Banded
Edit Distance (Ukkonen's Algorithm), which skips any cell provably too far off the main diagonal
to matter once only answers within a fixed budget k are of interest. For a version that
keeps this exact table shape but adds a fourth edit operation, see
Damerau–Levenshtein Distance, which lets swapping
two adjacent characters count as a single edit instead of two substitutions.
This site's guide, Choosing a Dynamic Programming Approach, compares this entry against the other ten Dynamic Programming entries side by side.