Levenshtein Distance: Formula, Worked Table, Python Code and Timings
Levenshtein distance counts the minimum number of single-character insertions, deletions and substitutions needed to turn one string into another. Fill the dynamic programming table by hand, code it in Python with two rows of memory, and learn where it powers spell checks, fuzzy search and test assertions.
- Levenshtein distance is the minimum number of insertions, deletions and substitutions to turn string A into string B. kitten to sitting is 3.
- It is computed with a dynamic programming table in O(m × n) time; keeping only two rows cuts memory to O(n).
- Swapped letters cost 2 in Levenshtein but 1 in the Damerau variant: recieve to receive was 2 vs 1 in our test.
- Pure Python took 372 ms to compare two 1,000-character strings, so use a C library or pre-filtering for large jobs.
A user types “chekout” into your search box. A test compares an error message that differs by one character. A data pipeline needs to match “Jon Smith” with “John Smith”. All three need a number that says how different two strings are. Levenshtein distance, also called edit distance, is the classic answer, and it is simple enough to compute by hand.
In this guide we fill the table step by step, then implement it in Python and test it. Every result came from running the code with Python 3.13.6. If you have read our guides to Jaccard similarity and cosine similarity, this is the character-level member of the same family.
What Levenshtein distance measures
The Soviet mathematician Vladimir Levenshtein defined the measure in 1965. It counts the smallest number of single-character edits needed to change one string into the other. Identical strings have distance 0. The distance can never be larger than the length of the longer string, because you could always substitute every character and insert or delete the rest.
Unlike Jaccard or cosine similarity, which compare sets or vectors and ignore order, Levenshtein distance respects the order of characters. “listen” and “silent” contain the same letters but are several edits apart.
The three edit operations
| Operation | Example | Cost |
|---|---|---|
| Insertion | cat to cart (insert r) | 1 |
| Deletion | cart to cat (delete r) | 1 |
| Substitution | cat to cut (a becomes u) | 1 |
Every operation costs 1 in the standard version. Weighted variants exist, for example making substitutions between neighbouring keyboard keys cheaper, but the standard definition is what libraries and interview questions mean.
The recurrence
Let d[i][j] be the distance between the first i characters of A and the first j characters of B. Then:
d[i][0] = i # delete all i characters
d[0][j] = j # insert all j characters
d[i][j] = min(
d[i-1][j] + 1, # deletion
d[i][j-1] + 1, # insertion
d[i-1][j-1] + cost # substitution, cost 0 if A[i] == B[j] else 1
)
Each cell depends only on the cell above, the cell to the left and the cell diagonally up-left. That is what makes it a dynamic programming problem: you solve small prefixes first and reuse their answers, instead of trying every possible sequence of edits, which would grow exponentially.
Worked table: kitten to sitting
Rows are the letters of “kitten”, columns the letters of “sitting”. The extra first row and column represent the empty string. Our code printed this table:
s i t t i n g
0 1 2 3 4 5 6 7
k 1 1 2 3 4 5 6 7
i 2 2 1 2 3 4 5 6
t 3 3 2 1 2 3 4 5
t 4 4 3 2 1 2 3 4
e 5 5 4 3 2 2 3 4
n 6 6 5 4 3 3 2 3
Read a few cells to see the logic:
- Row k, column s: k and s differ, so take the diagonal 0 plus 1. Distance 1: substitute k with s.
- Row i, column i: the letters match, so copy the diagonal value of 1 at no cost.
- Row e, column i: e and i differ; the diagonal is 1, so the cell is 2.
- Bottom-right: 3, the final answer.
The diagonal of zero-cost matches (i, t, t, n) is why the distance is so small despite the words being different lengths.
Recovering the actual edits
The table gives the number, but you can also walk back from the bottom-right corner, choosing at each step the neighbour that produced the value. Our traceback found:
3 ['substitute k->s', 'substitute e->i', 'insert g']
That is exactly the textbook answer: kitten to sitten, sitten to sittin, sittin to sitting. Showing the edits is useful in diff tools and in test failure messages, where “expected X, got Y” is less helpful than “the third character changed”.
Python code with two rows of memory
A full table needs (m + 1) × (n + 1) cells. To get just the distance you only ever need the previous row, so this version keeps two:
def lev(a, b):
if len(a) < len(b):
a, b = b, a # make b the shorter string
prev = list(range(len(b) + 1))
for i, ca in enumerate(a, 1):
cur = [i]
for j, cb in enumerate(b, 1):
cur.append(min(prev[j] + 1, # deletion
cur[j - 1] + 1, # insertion
prev[j - 1] + (ca != cb))) # substitution
prev = cur
return prev[-1]
Swapping so that b is the shorter string keeps the rows as short as possible. The expression (ca != cb) is a boolean, which Python treats as 0 or 1, so it doubles as the substitution cost. This is the same row-by-row idea used in many iterator-based algorithms: process one row, keep only what the next row needs.
More examples we ran
| A | B | Distance | Why |
|---|---|---|---|
| flaw | lawn | 2 | delete f, insert n |
| (empty) | abc | 3 | three insertions |
| same | same | 0 | identical |
| Python | python | 1 | case matters: P vs p |
| ab | ba | 2 | a swap costs two substitutions |
| cafe | café | 1 | e vs é |
The Python row is a reminder to normalise case first if case should not count, for example with a.lower() or, better for international text, a.casefold().
From distance to a similarity score
A raw distance of 3 means a lot for a five-letter word and little for a paragraph. Dividing by the longer length gives a score between 0 and 1:
def sim(a, b):
return 1 - lev(a, b) / max(len(a), len(b), 1)
sim("kitten", "sitting") # 0.571
difflib.SequenceMatcher(None, "kitten", "sitting").ratio() # 0.615
Python’s built-in difflib gave a different number because it uses a different algorithm, based on matching blocks rather than edit distance. Neither is wrong, but they are not interchangeable, so pick one and use it consistently, especially when you set thresholds like “accept matches above 0.8”.
Tip: the max(..., 1) guard avoids dividing by zero when both strings are empty. Two empty strings are identical, so their similarity should be 1.
Spell suggestions in a few lines
Rank candidate words by distance to what the user typed:
words = ["checkout", "checklist", "check-in", "kitchen", "chicken", "cheque"]
q = "chekout"
sorted((lev(q, w), w) for w in words)[:3]
# [(1, 'checkout'), (3, 'cheque'), (4, 'check-in')]
difflib.get_close_matches(q, words, n=3)
# ['checkout', 'checklist', 'cheque']
Both put “checkout” first, which is the right answer, but the runners-up differ. Real search engines combine edit distance with word frequency and keyboard layout, and for whole documents they switch to token-based ranking such as BM25 or TF-IDF.
Transpositions: the Damerau variant
Swapping two neighbouring letters is one of the most common typing mistakes, yet Levenshtein charges 2 for it. The optimal string alignment version of Damerau-Levenshtein adds a fourth operation, a transposition of adjacent characters, with cost 1. We implemented it and compared:
ab / ba: Levenshtein 2, Damerau (OSA) 1
recieve / receive: Levenshtein 2, Damerau (OSA) 1
For spell checking human typing, the Damerau version usually gives better rankings. For DNA sequences or comparing machine output, plain Levenshtein is the norm.
A Unicode trap
The letter é can be stored as one code point, or as e followed by a combining accent. They look identical on screen:
c1 = "café" # é as one code point
c2 = "café" # e + combining accent
len(c1), len(c2), lev(c1, c2) # 4 5 2
lev(unicodedata.normalize("NFC", c1), unicodedata.normalize("NFC", c2)) # 0
Without normalisation, two visually identical strings were 2 edits apart. Normalise with unicodedata.normalize("NFC", s) before comparing user-entered text. Our UTF-8 encoding guide explains why the same character can have several byte forms.
Speed we measured
The algorithm does work proportional to m × n. With our pure Python function on one Windows laptop:
1000 x 1000 characters: 372 ms
2000 x 2000 characters: 1061 ms
Doubling both lengths roughly tripled the time in this run, close to the four times that O(m × n) predicts once overhead is counted; a second run took 1,396 ms, so expect noise. For single words this is instant, but comparing a long list of names against another long list in pure Python will crawl. In production, use a C-accelerated library such as RapidFuzz or python-Levenshtein, stop early when the distance passes a threshold, or pre-filter candidates by length, since strings whose lengths differ by more than k cannot be within distance k. We did not benchmark those libraries here.
Where Levenshtein distance is used
- Spell checking and “did you mean” suggestions in search boxes.
- Fuzzy matching and deduplication of names, addresses and product titles.
- Testing: asserting that an AI or OCR output is “close enough” to the expected text, or flagging near-duplicate test cases.
- Bioinformatics: comparing DNA and protein sequences, usually with weighted costs.
- Evaluating models: character and word error rates for speech recognition are edit distances divided by length.
For meaning rather than spelling, character edits are the wrong tool: “car” and “automobile” are far apart by Levenshtein but close in meaning, which is what embeddings capture.
Final thoughts
Levenshtein distance is a small dynamic programming algorithm with a big range of uses. Fill the table once by hand and the recurrence becomes obvious; code it with two rows to save memory; normalise case and Unicode before comparing; and switch to the Damerau variant when transposed letters matter. For large workloads, reach for a compiled library and length-based pre-filtering instead of pure Python loops.
Frequently asked questions
What is Levenshtein distance in simple terms?
It is the smallest number of single-character insertions, deletions and substitutions needed to turn one string into another. For example, kitten to sitting has a distance of 3.
What is the time complexity of Levenshtein distance?
The standard dynamic programming algorithm runs in O(m times n) time, where m and n are the string lengths. Memory can be reduced to O(n) by keeping only two rows of the table.
What is the difference between Levenshtein and Damerau-Levenshtein?
Damerau-Levenshtein also allows swapping two adjacent characters as a single edit. In our test, recieve to receive was 2 with Levenshtein and 1 with the Damerau variant.
How do I turn Levenshtein distance into a similarity percentage?
Divide the distance by the length of the longer string and subtract the result from 1. Kitten and sitting give 1 minus 3 divided by 7, which is about 0.571.
Is Levenshtein distance case sensitive?
Yes. Python and python have a distance of 1. Convert both strings with lower or casefold, and normalise Unicode, before comparing if case and accents should not count.
Keep learning
Need help with testing, WordPress or SEO?
We help teams ship better software and grow their sites. Tell us what you are working on and we will suggest a clear next step.