Tool · 2026-07-22
Levenshtein, cell by cell.
The edit distance between two strings is the smallest number of single-character insertions, deletions and substitutions that turns one into the other. Dynamic programming fills a table where cell (i, j) holds the answer for the first i characters of one string and the first j of the other. The number in the bottom-right corner is the distance. Walk backwards along the arrows and the exact sequence of edits comes out.
The recurrence
The first row and column are filled by hand: turning a prefix into the empty string costs one deletion per character, and vice versa. Every other cell (i, j) takes the minimum of three neighbours plus a step cost. The cell above plus one is a deletion. The cell to the left plus one is an insertion. The diagonal cell plus zero (if the two characters match) or plus one (if they do not) is a substitution or a free copy.
The traceback
The path highlighted in amber goes from the bottom-right corner back to the top-left, one step at a time. At each cell it picks the neighbour whose value plus the step cost matches the current cell. A diagonal step is a match or a substitution, a step up is a deletion, a step left is an insertion. Reversing the path gives you the edit script printed below the table. When several neighbours are tied, the trace here prefers matches, then substitutions, then insertions, then deletions. Other tie-breaks give different scripts of the same length.
Where it shows up
Spell-checkers rank suggestions by edit distance from the typed word. Diff tools use a close relative (Longest Common Subsequence) to line up matching lines. Bioinformatics uses a weighted variant, Needleman-Wunsch, to align DNA. Fuzzy search libraries index strings by a distance-preserving hash so neighbours can be found without filling the full table. The table itself is only used when you need the exact script, not just the number.
Sources
- Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10(8), 707–710. The original paper, in the context of coding theory.
- Wagner, R. A. and Fischer, M. J. (1974). The String-to-String Correction Problem. Journal of the ACM, 21(1), 168–173. The dynamic programming formulation used here.
- Ukkonen, E. (1985). Algorithms for approximate string matching. Information and Control, 64(1–3), 100–118. The band-limited variant that runs in O(nd) when the strings are close.