Edit distance · dynamic programming

Find a minimum edit sequence and follow its prefix-distance table one cell at a time.

About this tool

Turn one text into another

Enter a source and target, each containing 0…20 well-formed Unicode code points. Empty texts are valid. Calculate shows the complete table, minimum distance and one optimal edit sequence. Step starts a new table when needed and reveals exactly one cell, row by row. Revealing the last cell completes the result immediately. Clear result keeps the input texts; editing a text or changing the example clears the old result.

How the table works

Row i means the first i code points of the source; column j means the first j code points of the target. Header indices show the prefix length, followed by the last code point of that prefix. ∅ is the empty prefix. D[0,j] = j insertions and D[i,0] = i deletions. An inner cell chooses the minimum of the diagonal value plus 0 for a match or 1 for replacement, the value above plus 1 for deletion, and the value to the left plus 1 for insertion.

The current cell lists the candidates and marks its chosen predecessor. Ties prefer the diagonal, then deletion, then insertion. The highlighted final path connects (0,0) to the lower-right cell. It selects one deterministic optimal sequence; other optimal sequences may exist. Swapping two neighboring characters is not a separate operation: ab → ba has distance 2 here.

Read the edit sequence

Each listed change costs 1. Matches cost 0 and appear in Full alignment. Positions start at 0 in the text immediately before that operation, measured in code points. The text afterwards shows the entire current text, not just its changed character. For kitten → sitting the minimum distance is 3: replace k with s at position 0 to get sitten, replace e with i at position 4 to get sittin, then insert g at position 6 to get sitting.

Alignment gaps are labelled Gap. A literal hyphen remains a character, shown with U+002D, and is never used to represent a gap. Change numbers count actual edits; the step numbers in Full alignment also count matches.

Unicode and exact text

The calculation uses code points, not UTF-16 code units or visual grapheme clusters. 😀 → empty has distance 1, while 👩‍💻 contains three code points. Composed é and e followed by U+0301 are distinct inputs. There is no normalization, trimming, case conversion or silent truncation. Unpaired UTF-16 surrogates are rejected.

Each non-alphanumeric character has a U+… code label in the matrix or alignment. □ stands for a whitespace or invisible character; its code identifies which one. A dotted circle supports a combining mark and is not part of the source text. Intermediate texts preserve their actual whitespace; their code notes use zero-based positions. Bidirectional isolation keeps right-to-left characters and direction controls from rearranging surrounding labels.

Sources