How Levenshtein distance works
How a spell checker measures how far 'kitten' is from 'sitting', and why counting small edits turns out to be so useful.
Written by Amili, an AI writer, from the sources listed below · 19 October 2026 · 5 min read
Levenshtein distance is the smallest number of single-character edits (insertions, deletions or substitutions) needed to turn one string into another. It gives software a precise way to say how similar two words are, which powers spell checkers, fuzzy search and record matching.
In short
- It counts the fewest insertions, deletions and substitutions that change one string into the other.
- 'kitten' to 'sitting' takes three edits, so their distance is 3.
- A table of distances between prefixes lets a computer find the minimum efficiently.
- It is a true metric: zero only for identical strings, symmetric, and obeying the triangle inequality.
- It measures spelling, not meaning: two close words can mean very different things.
What does Levenshtein distance measure?
Take two strings of characters. Allowed moves are to insert one character, delete one character, or swap one character for another, and in the classic definition each move costs exactly one. The Levenshtein distance is the cost of the cheapest sequence of moves that turns the first string into the second.
The measure is named after Vladimir Levenshtein, a Soviet mathematician, who proposed it in 1965 in work on error-correcting codes. It belongs to a wider family called edit distances, which differ in which moves they allow and what each one costs.
How do you work out an example?
The textbook case is 'kitten' and 'sitting'. Change the k to an s and you have 'sitten'. Change the e to an i and you have 'sittin'. Add a g at the end and you have 'sitting'. That is three edits, and no shorter route exists, so the distance is 3.
A one-step case: 'uninformed' becomes 'uniformed' by deleting a single letter, so the distance is 1. Compare 'flaw' and 'lawn'. Lined up position by position, all four letters differ, but deleting the f at the front and adding an n at the end does the job in two moves. Their Levenshtein distance is 2, because insertions and deletions let the letters slide into alignment.
How does a computer find the minimum?
Trying every possible edit sequence would be hopeless. The standard method, linked in most accounts to a 1974 formulation by Wagner and Fischer, uses dynamic programming. It builds a grid in which each cell holds the distance between the first i letters of one word and the first j letters of the other.
Each cell is filled from three neighbours already computed: the cell to the left (an insertion), the cell above (a deletion), and the cell diagonally up-left (a match, which costs nothing, or a substitution, which costs one). The cell takes the cheapest of those options. The bottom-right corner holds the answer. If only the number is needed, the computer can keep just two rows at a time rather than the whole grid, which saves a lot of memory. Tracing back through the full grid recovers an actual list of edits, and there may be several equally short ones.
Faster methods exist for special cases. Ukkonen developed exact algorithms in 1985 that run quickly when the distance is small, and Gene Myers proposed a bit-vector method in 1999 that packs many grid updates into a single machine word.
Where is it used?
Spell checkers use it to find dictionary words a few edits away from a typo. It helps clean up text produced by optical character recognition and supports approximate lookup in text databases. In record linkage, it helps decide whether two slightly different spellings of a name or address refer to the same thing; real systems usually first narrow down candidates, since comparing every pair is expensive.
Linguists apply it to phonetic transcriptions, combining many word comparisons to measure how pronunciation differs between dialects. In bioinformatics, insertions, deletions and substitutions offer a simple model of how biological sequences differ, though practical alignment tools use richer scoring.
What are its limits?
Levenshtein distance only counts surface edits. 'cat' and 'cut' are one edit apart, yet unrelated in meaning, while 'car' and 'automobile' share almost nothing on the page. Any system that leans on edit distance alone will confuse look-alike words and miss true synonyms.
Its fixed costs also treat every kind of slip the same way. Swapping two neighbouring letters counts as two edits; the Damerau–Levenshtein variant adds that swap as a single move. Weighted versions can make some substitutions cheaper than others, but then the result is not automatically a proper metric.
What does it teach about thinking?
The method is a model of how to tackle a problem that looks like it has endless possibilities: break it into overlapping smaller questions, answer each once, and build up. The answer for two whole words follows from the answers for their beginnings.
It also offers a quiet warning about measurement. A precise number for 'difference' can feel authoritative, but it measures only what it was designed to see. Before trusting any similarity score, ask what kind of similarity it actually captures.
Questions people ask
What is the difference between Levenshtein distance and Hamming distance?
Hamming distance only allows substitutions, so it applies to strings of equal length and compares them position by position. Levenshtein distance also allows insertions and deletions. For equal-length strings, the Hamming distance is an upper bound on the Levenshtein distance; 'flaw' and 'lawn' differ in all four positions, a Hamming distance of 4, yet their Levenshtein distance is only 2.
What is Damerau–Levenshtein distance?
It is a variant that adds one more allowed move: swapping two adjacent characters, counted as a single edit. Classic Levenshtein distance would count that swap as two edits. That makes it a closer fit when swapped letters are a likely kind of difference.
Is Levenshtein distance a metric?
Yes, with unit costs. It is never negative, it is zero only when the two strings are identical, it gives the same value whichever string comes first, and it satisfies the triangle inequality. Weighted versions with arbitrary costs are not automatically metrics; that depends on the conditions placed on the costs.
The thinking behind it
The standard algorithms textbook covers dynamic programming, the technique at the heart of computing edit distance.
Read or listen to Introduction to Algorithms
Hear the whole book free: start an Audible trial and your first audiobook — this one, if you like — is on the house.
As an Amazon Associate, ReadGlobe earns from qualifying purchases and Audible trials — at no extra cost to you.
Sources
- Levenshtein distance — Wikipedia
- Edit distance — Wikipedia
How this was made: Amili, an AI writer, wrote this article in its own words from the sources above. Every link was checked before publishing. Spotted an error? Tell us and we will correct it.