The idea: how many edits apart are two words?

The edit distance (or Levenshtein distance) between two strings is the fewest single-letter edits that turn one into the other. There are three edits, and each costs 1: insert a letter, delete a letter, or substitute one letter for another. kitten and sitting are 3 apart: substitute k→s, substitute e→i, insert g. Writing the two words one above the other, with a gap where a letter is inserted or deleted, is called an alignment.

kitten aligned over sitting in seven columns: k over s marked S, i t t matched, e over i marked S, n matched, a gap over g marked I. The edits read kitten, sitten, sittin, sitting: 2 substitutions and 1 insertion.
An alignment lists every column as a match, a substitution, an insert or a delete; the edit distance is the number of non-matches.

Trying every alignment is hopeless: there are exponentially many. Dynamic programming solves it with a table of answers for every pair of prefixes, filled from the smallest up. The page shows that table filling cell by cell, then the traceback that turns the final number back into the edits.

The recurrence: three neighbours

Let the source be s (length m, the rows) and the target t (length n, the columns). D[i][j] is the edit distance between the first i letters of s and the first j letters of t. Look at how the best alignment of those two prefixes ends. Its last column is one of three things:

  • ↖ match or substitute: si sits over tj. That costs 0 if the letters are equal and 1 if not, plus the best alignment of the shorter prefixes, D[i-1][j-1].
  • ↑ delete: si sits over a gap. Cost 1 + D[i-1][j].
  • ← insert: a gap sits over tj. Cost 1 + D[i][j-1].
D[0][j] = j                         (insert j letters)
D[i][0] = i                         (delete i letters)
D[i][j] = min( D[i-1][j-1] + (s[i] == t[j] ? 0 : 1),    ↖ match / substitute
               D[i-1][j]   + 1,                          ↑ delete s[i]
               D[i][j-1]   + 1 )                         ← insert t[j]
Cell D[2][3] for kitten and sitting, turning ki into sit, with its three neighbours: the diagonal 2 gives substitute i to t, 2 + 1 = 3; the cell above 3 gives delete i, 3 + 1 = 4; the cell to the left 1 gives insert t, 1 + 1 = 2, the smallest, so D[2][3] = 2.
Every cell reads three finished neighbours and keeps the cheapest; here inserting t wins.

Filling the table

Row 0 and column 0 are free: turning the empty string into j letters takes j inserts, and turning i letters into nothing takes i deletes. After that, the page fills row by row, left to right, so the three cells a cell needs (up-left, up, left) are always done. In the animation the cell being filled has a red ring, its three neighbours are blue, the cheapest one is darker blue, and the current cell panel shows the three sums. The answer is the bottom-right cell, D[m][n]. (Demo: kitten → sitting)

Choose one row per step to fill a whole row at once when the words are longer. (Demo: intention → execution)

Traceback: from the number to the edits

The table gives the distance, not the edits. To recover them, start at D[m][n] and repeatedly step to a neighbour that could have produced the cell's value: up-left if D[i][j] = D[i-1][j-1] + cost, else up if D[i][j] = D[i-1][j] + 1, else left. Each step is one column of the alignment, read right to left, and the walk ends at D[0][0]. The path cells turn yellow and the alignment panel grows one column per step.

  • Deletes are vertical steps. horse → ros: substitute h→r, keep o, delete r, keep s, delete e. (Demo: horse → ros)
  • Inserts are horizontal steps. sunday → saturday: keep s, insert a and t, keep u, substitute n→r, keep day. (Demo: sunday → saturday)
  • A delete and an insert can be cheaper than substitutions when the letters only shift: flaw → lawn is delete f, keep law, insert n, distance 2 instead of 4 substitutions. (Demo: flaw → lawn)

Often several neighbours tie, so there can be several optimal alignments with the same cost. The page always prefers ↖, then ↑, then ←. For intention → execution that gives five substitutions (i→e, n→x, t→e, e→c, n→u), while the textbook alignment uses a delete, three substitutions and an insert; both cost 5.

Worked example

The full table for kitten → sitting. Rows are the source prefixes, columns the target prefixes:

         ε   s   i   t   t   i   n   g
    ε    0   1   2   3   4   5   6   7
    k    1   1   2   3   4   5   6   7
    i    2   2   1   2   3   4   5   6
    t    3   3   2   1   2   3   4   5
    t    4   4   3   2   1   2   3   4
    e    5   5   4   3   2   2   3   4
    n    6   6   5   4   3   3   2   3

The answer is D[6][7] = 3. Walking back: 3 came from the left (insert g), 2 from the diagonal with n = n (match), 2 from the diagonal with e ≠ i (substitute), then t, t, i match down the diagonal, and k ≠ s is the last substitution at D[1][1] = 1.

Running time and memory

The table has (m + 1)(n + 1) cells and each takes constant time, so the algorithm (often called Wagner–Fischer) runs in Θ(mn) time and space. Each row only needs the row above it, so two rows, Θ(min(m, n)) memory, are enough for the number. The traceback needs the whole table, or Hirschberg's divide-and-conquer trick, which recovers the alignment in linear space.

Variants

distanceallowed editsnotes
Levenshteininsert, delete, substitute (cost 1 each)this page
indel / LCS distanceinsert, delete onlyequals m + n − 2 × LCS length
Damerau–Levenshteinalso swap two adjacent letterscatches typos like "teh"
Hammingsubstitute onlyequal-length strings, no table needed
weighted (Needleman–Wunsch)any costs or scores per pairDNA and protein alignment

Edit distance is behind spelling suggestions ("did you mean …"), fuzzy search, diff-style comparisons and sequence alignment in biology.

See also Longest Common Subsequence, which fills a very similar table and traces back the same way, and 0/1 Knapsack, another table-plus-traceback dynamic program.

in "Variants" (after the diff-style comparisons sentence): "Version control builds on diffs: see Git Three-Way Merge for how Git combines two branches' changes against their merge base.

What the page leaves out

Strings are limited to 9 lowercase letters so the table fits on the canvas. The page leaves out costs other than 1 (for example substitution cost 2, which makes the distance the indel distance), adjacent swaps (Damerau), the two-row and Hirschberg memory savings, banded tables that stop early when only a small distance matters, listing every optimal alignment instead of one, and the top-down memoized version of the same recurrence.