Tools Suite

Dynamic programming

O(m · n)·O(m · n) space
Whole table

Drag to pan; pinch or Ctrl+scroll to zoom, which stops at the whole table; arrow keys pan once the picture has focus. The headers stay put while you pan.

the empty first prefix, the empty second prefix, not yet filledthe empty first prefix, column 1, ‘s’, not yet filledthe empty first prefix, column 2, ‘i’, not yet filledthe empty first prefix, column 3, ‘t’, not yet filledthe empty first prefix, column 4, ‘t’, not yet filledthe empty first prefix, column 5, ‘i’, not yet filledthe empty first prefix, column 6, ‘n’, not yet filledthe empty first prefix, column 7, ‘g’, not yet filledrow 1, ‘k’, the empty second prefix, not yet filledrow 1, ‘k’, column 1, ‘s’, not yet filledrow 1, ‘k’, column 2, ‘i’, not yet filledrow 1, ‘k’, column 3, ‘t’, not yet filledrow 1, ‘k’, column 4, ‘t’, not yet filledrow 1, ‘k’, column 5, ‘i’, not yet filledrow 1, ‘k’, column 6, ‘n’, not yet filledrow 1, ‘k’, column 7, ‘g’, not yet filledrow 2, ‘i’, the empty second prefix, not yet filledrow 2, ‘i’, column 1, ‘s’, not yet filledrow 2, ‘i’, column 2, ‘i’, not yet filledrow 2, ‘i’, column 3, ‘t’, not yet filledrow 2, ‘i’, column 4, ‘t’, not yet filledrow 2, ‘i’, column 5, ‘i’, not yet filledrow 2, ‘i’, column 6, ‘n’, not yet filledrow 2, ‘i’, column 7, ‘g’, not yet filledrow 3, ‘t’, the empty second prefix, not yet filledrow 3, ‘t’, column 1, ‘s’, not yet filledrow 3, ‘t’, column 2, ‘i’, not yet filledrow 3, ‘t’, column 3, ‘t’, not yet filledrow 3, ‘t’, column 4, ‘t’, not yet filledrow 3, ‘t’, column 5, ‘i’, not yet filledrow 3, ‘t’, column 6, ‘n’, not yet filledrow 3, ‘t’, column 7, ‘g’, not yet filledrow 4, ‘t’, the empty second prefix, not yet filledrow 4, ‘t’, column 1, ‘s’, not yet filledrow 4, ‘t’, column 2, ‘i’, not yet filledrow 4, ‘t’, column 3, ‘t’, not yet filledrow 4, ‘t’, column 4, ‘t’, not yet filledrow 4, ‘t’, column 5, ‘i’, not yet filledrow 4, ‘t’, column 6, ‘n’, not yet filledrow 4, ‘t’, column 7, ‘g’, not yet filledrow 5, ‘e’, the empty second prefix, not yet filledrow 5, ‘e’, column 1, ‘s’, not yet filledrow 5, ‘e’, column 2, ‘i’, not yet filledrow 5, ‘e’, column 3, ‘t’, not yet filledrow 5, ‘e’, column 4, ‘t’, not yet filledrow 5, ‘e’, column 5, ‘i’, not yet filledrow 5, ‘e’, column 6, ‘n’, not yet filledrow 5, ‘e’, column 7, ‘g’, not yet filledrow 6, ‘n’, the empty second prefix, not yet filledrow 6, ‘n’, column 1, ‘s’, not yet filledrow 6, ‘n’, column 2, ‘i’, not yet filledrow 6, ‘n’, column 3, ‘t’, not yet filledrow 6, ‘n’, column 4, ‘t’, not yet filledrow 6, ‘n’, column 5, ‘i’, not yet filledrow 6, ‘n’, column 6, ‘n’, not yet filledrow 6, ‘n’, column 7, ‘g’, not yet filledthe empty second prefix—0column 1, ‘s’s1column 2, ‘i’i2column 3, ‘t’t3column 4, ‘t’t4column 5, ‘i’i5column 6, ‘n’n6column 7, ‘g’g7the empty first prefix—0row 1, ‘k’k1row 2, ‘i’i2row 3, ‘t’t3row 4, ‘t’t4row 5, ‘e’e5row 6, ‘n’n6→ second↓ first

The table has 7 rows and 8 columns, and nothing has been worked out yet. Three edits are allowed and each one is a different neighbour, so every cell reads three cells rather than two.

The table has 7 rows and 8 columns, and nothing has been worked out yet. Three edits are allowed and each one is a different neighbour, so every cell reads three cells rather than two.
Answer so far—

D(i, j) = a[i] = b[j] ? D(i−1, j−1) : 1 + min( D(i−1, j), D(i, j−1), D(i−1, j−1) )

  1. 1fill the first row and the first column with 0, 1, 2 and so on, since turning a prefix into nothing costs one deletion per character
  2. 2the two characters match, so copy the cell diagonally back unchanged: no edit is needed
  3. 3the characters differ, so read all three neighbours
  4. 4take the smallest and add one, and remember which edit that was
  5. 5walk back, reading each step as the edit it stood for
  6. 6stop: the bottom-right cell is the edit distance, and the walk back is the list of edits
Cells filled
0
Cells read
0
Values written
0

Complexity

BestO(m · n)
AverageO(m · n)
WorstO(m · n)
Extra spaceO(m · n)
3 · m × n at n=56 predicts 168; this run took 0.

Edit distance

This is the Levenshtein distance. The table holds, for every pair of prefixes, the fewest single-character edits that turn one into the other. Three edits are allowed and each corresponds to one neighbour: delete a character from the first string, which is the cell above; insert one from the second, which is the cell to the left; or substitute one for the other, which is the cell diagonally back. Where the two characters already agree, the diagonal costs nothing.

Its recurrence

D(i, j) = a[i] = b[j] ? D(i−1, j−1) : 1 + min( D(i−1, j), D(i, j−1), D(i−1, j−1) )

When it is the right choice

Spelling correction, fuzzy search, "did you mean", record deduplication, and measuring how far apart two versions of a sequence are. It is also the honest way to score an approximate match where a pattern matcher would say only yes or no. Its cost is the product of the two lengths, so comparing long documents wants a banded or a heuristic variant rather than the whole table.

How it works

Worth noticing

Cost

Best
O(m · n)
Average
O(m · n)
Worst
O(m · n)
Extra space
O(m · n)
Table
two dimensions
Accepts
up to 16 characters in each string

The limits are pedagogical rather than technical: this tool keeps the whole table in every recorded step, so the shape of the table sets the size of the trace directly, and a run has to stay short enough to sit and watch. An input that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the input sizes rather than by running it and finding out.

An unfilled cell is drawn differently from a cell holding a zero — no fill, a dashed outline, and no number at all — because early in a run that difference is most of the picture.

Worth comparing

All dynamic programming algorithms