The Levenshtein distance between two sequences is the minimum number of single-element insertions, deletions and substitutions needed to turn one into the other. A dynamic-programming table finds that minimum by solving the problem for every pair of prefixes. The score is meaningful only after you decide what counts as an element—such as a byte, Unicode code point, grapheme cluster or token—and whether to normalize the inputs first.
What is the Levenshtein distance algorithm?
Standard, unit-cost Levenshtein distance compares two sequences using three allowed edits: insert one element, delete one element, or substitute one element for another. Each edit costs 1; matching elements costs 0. The distance is the smallest total cost among all ways to transform the first sequence into the second. The Stanford-hosted Introduction to Information Retrieval chapter defines edit distance in these terms and explains the prefix-based computation.
| # | Preview | Product | Price | |
|---|---|---|---|---|
| 1 |
|
The Algorithm Design Manual (Texts in Computer Science) | $53.97 | Buy on Amazon |
| 2 |
|
Algorithm Design | $222.95 | Buy on Amazon |
| 3 |
|
50 Algorithms Every Programmer Should Know: Tackle computer science challenges with classic to... | $33.77 | Buy on Amazon |
| 4 |
|
The Algorithm Design Manual | $40.70 | Buy on Amazon |
| 5 |
|
Algorithms (4th Edition) | $68.77 | Buy on Amazon |
For example, the distance from cat to dog is 3: replace each of the three letters. A lower score means fewer edits under this particular model; it does not necessarily mean the words have similar meanings.
How do you calculate edit distance between two strings?
Let sequence A have length m and sequence B have length n. Define D[i,j] as the minimum cost of changing the first i elements of A into the first j elements of B. The empty-prefix cases are:
Outdated Drivers Are Slowing You Down
One free scan finds every outdated or missing driver and matches the right update for your exact hardware.Free scan · exact hardware matchPC Slower Than It Used to Be?
A free scan shows the junk files, broken settings and background clutter dragging Windows down - then fixes them in one click.Free scan · Windows 10 & 11#1 Best Overall
D[0,0] = 0: no edits are needed to change an empty sequence into itself.D[i,0] = i: delete allielements ofA‘s prefix.D[0,j] = j: insert alljelements ofB‘s prefix.
For nonempty prefixes, fill each cell with the least expensive of three possibilities:
D[i,j] = min(D[i-1,j] + 1, D[i,j-1] + 1, D[i-1,j-1] + cost)
Here, cost is 0 if the elements being compared match and 1 if they differ. The three candidates correspond to deleting an element from A, inserting an element from B, or matching/substituting the two elements. After filling the table, D[m,n] is the distance. This recurrence and matrix approach are described in the Stanford chapter.
Rank #2
Worked example: “kitten” to “sitting”
Using unit-cost character substitutions and insertions, one minimum-cost transformation is:
Do these 3 things before closing this tab:
1Fix the driver behind crashes, sound loss and screen glitches2Clear out junk files and repair common Windows errors3Scan for outdated or missing drivers - takes under a minute- Substitute
kwiths:kittenbecomessitten. - Substitute
ewithi:sittenbecomessittin. - Insert
gat the end:sittinbecomessitting.
That gives a cost of 3. The recurrence establishes that no cheaper sequence of allowed edits exists; the answer is not simply the number of positions that differ, since insertions and deletions can shift later elements.
What does the result cost to compute?
The straightforward dynamic program computes a constant amount of work for each of the m × n prefix pairs, so it takes O(mn) time. A full table also takes O(mn) memory. Implementation guidance describes alternatives for workloads that need less memory or only a bounded answer.
- Need only the score: Keep the previous and current rows rather than the whole table. Since the recurrence only needs the prior row and the current row’s preceding cell, working memory can be reduced to
O(min(m,n)). - Need an edit script: Save predecessor choices while computing, or recompute information during traceback. When several choices have the same minimum cost, a deterministic tie-breaking rule is needed if the returned script must be stable.
- Need only to know whether distance is at most
k: For unit-cost edits, a path of cost at mostkcannot stray more thankdiagonals from the main diagonal. A banded computation can skip cells outside that region. This is useful for a threshold decision, not a substitute for an exact unbounded score. - Have a specialized workload: Bit-vector methods can accelerate suitable unit-cost comparisons. For one query checked against many dictionary entries, a trie combined with a Levenshtein automaton may be appropriate. Neither is a universal replacement for the basic recurrence.
How does the algorithm handle Unicode characters?
Levenshtein distance operates on sequences, not on a universal definition of “character.” A programming language or library might expose a string as bytes, UTF-16 code units, Unicode code points, grapheme clusters (user-perceived characters), or tokens. These choices can produce different distances. For example, a displayed accented character may be represented by a single code point or by a base letter followed by a combining mark; comparing those representations as code points can yield a nonzero distance even when they look alike.
Normalization and case folding can also change the sequences before comparison. Decide whether to apply them, and state the policy alongside the chosen sequence unit. Do not describe a code-unit result as a “character” distance unless code units are what the application intends to count. The implementation guide discusses these representation choices.
Recommended Free Tools
Unicode collation is a separate concern. Collation rules compare and order text according to configurable distinctions such as alphabetic, diacritic and case levels; that is not the same operation as counting insertions, deletions and substitutions. See the Unicode Collation Algorithm report for the collation model.
Rank #4
What is the difference between Levenshtein and Damerau–Levenshtein distance?
Standard Levenshtein distance does not count swapping neighboring elements as one edit. To transform ab into ba, it takes two substitutions under the standard model. A Damerau–Levenshtein-style metric includes a transposition operation, so that swap can count as one. Implementations may differ in the exact transposition variant they use, so identify the metric before comparing scores. The implementation guide discusses transposition-aware variants.
Weighted edit distance is another variation: operations or symbol pairs can have different costs. This changes the interpretation of the result, and asymmetric insertion and deletion costs can make the distance direction-dependent. A score from a weighted or transposition-aware variant should not be compared as though it came from standard unit-cost Levenshtein distance. The Stanford chapter discusses weighted costs, and the implementation guide covers implementation variants.
Independent reader supportYour contribution helps us test, update, and keep practical guides available for everyone.What the distance can—and cannot—tell you
The score reports the minimum edit cost under the selected representation and operation costs. By itself, it does not measure meaning, account for keyboard-neighbor likelihood, or use language context. An application can combine edit distance with other signals, but those are additional methods, not properties of the metric.
What’s actually slowing this PC down?
Pick the symptom - the matching free tool is one click away.
Best Value
Before implementing or interpreting a result, make these choices explicit:
- What is one element: byte, code unit, code point, grapheme cluster or token?
- Are case folding or Unicode normalization applied before comparison?
- Are the operation costs standard and unit-weighted, or customized?
- Is the needed output an exact score, a threshold decision or an edit script?
- How long are the inputs, and what memory budget is available?
- Is the comparison for one pair or one query against a collection?
- Should adjacent transpositions count as one operation?
Where the algorithm comes from
Vladimir Levenshtein’s 1965 work on codes correcting deletions, insertions and reversals appeared in English translation in 1966. Wagner and Fischer’s 1974 paper, “The String-to-String Correction Problem,” is another foundational reference. Bibliographic details for both are available on the reference page.
Quick Recap
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
