Edit Distance: The Levenshtein DP Table

Defining "how different" two strings are

The Levenshtein distance between two strings is the minimum number of single-character insertions, deletions and substitutions needed to turn one into the other. It gives "kitten" → "sitting" a distance of 3: substitute k→s, substitute e→i, insert g. There is no cleverer sequence of edits that does it in fewer than 3 steps, and the DP table is what proves that.

The recurrence

Let dp[i][j] be the edit distance between the first i characters of string A and the first j characters of string B. Each cell only needs to consider three possible last moves — insert, delete, or match/substitute the final characters:

dp[0][j] = j                         // j inserts to build B from empty A
dp[i][0] = i                         // i deletes to reduce A to empty

dp[i][j] = dp[i-1][j-1]                          if A[i] == B[j]   (free match)
dp[i][j] = 1 + min(
             dp[i-1][j],      // delete A[i]
             dp[i][j-1],      // insert B[j]
             dp[i-1][j-1]     // substitute A[i] -> B[j]
           )                                     if A[i] != B[j]

Filling the grid row by row (or column by column), each cell is O(1) work given its three neighbours are already known, so the whole (n+1)×(m+1) table fills in O(nm) time and, in the naive version, O(nm) space. The final answer sits in the bottom-right corner, dp[n][m].

Backtracking the actual alignment

The number dp[n][m] alone only tells you how many edits are needed, not which ones. To recover the actual sequence, walk backward from the bottom-right cell: at each cell, check which of the (up to three) neighbouring cells it could have come from under the recurrence, and step to whichever one matches — a diagonal step is a match or substitution, an upward step is a deletion, a leftward step is an insertion. This traced path is exactly what a diff tool displays as a sequence of unchanged, added and removed characters.

Trimming the memory: Hirschberg's algorithm

Because each row of the DP table only depends on the row above it, computing just the value dp[n][m] needs only O(min(n,m)) space — keep two rows and discard the rest. Recovering the alignment normally seems to require keeping the whole table for backtracking, but Hirschberg's algorithm (1975) sidesteps this: it runs the row-only forward pass from A's start and a row-only backward pass from A's end simultaneously, finds the column where the two half-solutions meet optimally, splits the problem there, and recurses on each half. The result is the full alignment in the same O(nm) time but only O(n+m) space — the standard technique for aligning million-character genomic sequences where an O(nm) table would not fit in memory.

Where it shows up

Spellcheckers use edit distance to rank candidate corrections by how few edits away they are from a misspelled word. Command-line tools and version control systems use the closely related Longest Common Subsequence DP to compute diffs. Bioinformatics uses weighted variants — the Needleman-Wunsch (global) and Smith-Waterman (local) algorithms — where substitution costs come from a scoring matrix reflecting how biologically similar two amino acids or nucleotides are, and a gap (insertion/deletion) typically costs more to open than to extend.

Frequently asked questions

Try it live

Everything above runs in your browser — open Edit Distance and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.