1. Home
  2. Blog
  3. Artificial Intelligence

Artificial Intelligence

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.

9 min read
Levenshtein distance explained with a worked table, Python code and timings

Key takeaways

  • 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

Work with Stack Quora

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.

Keep reading

More guides on testing, AI & modern development

Enjoyed this article? Pick a topic and jump straight into our newest tutorials.

Artificial Intelligence

Levenshtein Distance: Formula, Worked Table and Python Code

Levenshtein distance explained: the edit operations, the dynamic programming table for kitten and sitting, Python code with two-row memory, normalised…

Read article →
Software Development

URL Encoding Explained: Spaces, Plus Signs and UTF-8

URL encoding explained with tested Python and JavaScript code: percent encoding, reserved characters, %20 vs plus, UTF-8 bytes, encodeURI vs…

Read article →
DevOps

Gitignore: Patterns, Negation and Fixing Tracked Files

A tested gitignore guide: pattern rules, leading and trailing slashes, negation with !, the ignored parent folder trap, git check-ignore…

Read article →
Software Testing

Acceptance Criteria: Given When Then Examples and Checklist

How to write acceptance criteria testers can run: rule-based and Given When Then formats, a worked discount code example turned…

Read article →
Software Testing

State Transition Testing: Diagram, Table and Example

State transition testing explained with a login lockout example: states, events, the diagram, the state table, valid and invalid transitions,…

Read article →
Databases & SQL

Second Highest Salary in SQL: 5 Tested Ways and the Tie Trap

Find the second highest salary in SQL five ways: MAX subquery, LIMIT OFFSET, DENSE_RANK, a correlated subquery and per department,…

Read article →
Databases & SQL

SQL ROW_NUMBER: Top N per Group, Dedupe and Pagination

SQL ROW_NUMBER explained with tested queries: PARTITION BY, top N per group, deleting duplicates, pagination, the tie trap and how…

Read article →
Software Development

JavaScript Set: Union, Intersection and Removing Duplicates

JavaScript Set explained with tested examples: add, has, delete, deduplicating arrays, the new union and intersection methods, equality rules and…

Read article →
Test Automation

Python Unittest: Assert Methods, setUp and Mocks With Examples

A practical Python unittest tutorial: TestCase, assert methods, setUp and tearDown, subTest, skips, expected failures and mock, with a test…

Read article →
Software Development

Python Map and Filter: Examples vs List Comprehensions

Python map and filter explained with tested examples: lazy map objects, multiple iterables, filter(None), chaining, and a timed comparison with…

Read article →
Artificial Intelligence

Jaccard Similarity: Formula, Python, MinHash

Jaccard similarity measures overlap between two sets as intersection over union. Work the formula, compute it in Python for words…

Read article →
Software Development

Unix Timestamp Explained: Seconds vs ms

A Unix timestamp counts seconds since 1 January 1970 UTC. Learn seconds vs milliseconds, converting in Python, JavaScript and SQL,…

Read article →
DevOps

Git Hooks: Pre-commit and Commit-msg Examples

Git hooks run scripts at key moments such as commit and push. See tested pre-commit, commit-msg and prepare-commit-msg hooks, sharing…

Read article →
Test Automation

API Testing in Python: Pytest + Requests Suite

Build an API testing suite in Python with pytest and requests: fixtures, status codes, headers, JSON schema validation, CRUD flows,…

Read article →
Software Testing

Test Design Techniques: 9 Methods + Examples

Test design techniques help you write fewer tests that catch more bugs. Learn 9 black-box, white-box and experience-based methods with…

Read article →
Databases & SQL

SQL Temporary Table: Create, Use and Drop It

SQL temporary tables store interim results for one session. Learn syntax for SQL Server, PostgreSQL, MySQL, Oracle and SQLite, session…

Read article →
Databases & SQL

SQL CROSS JOIN: Every Combination + Examples

SQL CROSS JOIN returns every combination of rows from two tables. See the row math, product variants, calendar grids that…

Read article →
Software Development

JavaScript Date: Format, Parse, Timezone Bugs

JavaScript Date explained with tested Node.js code: zero-based months, the date-only UTC parsing trap, toISOString, getTimezoneOffset, Intl formatting, date math…

Read article →
Software Development

Python Requests: GET, POST, Timeouts, Retries

Python requests explained with code tested against a local API: GET with params, POST json vs data, headers and auth,…

Read article →
Artificial Intelligence

TF-IDF Explained: Formula and Worked Example

TF-IDF scores a word by how often it appears in a document and how rare it is across all documents….

Read article →
DevOps

Git Tag: Create, Push and Delete Release Tags

Git tag explained with tested commands: annotated vs lightweight tags, listing and sorting, pushing with follow-tags, deleting local and remote…

Read article →
Test Automation

Pytest Coverage: pytest-cov and Branch Gaps

Measure pytest coverage with pytest-cov: term-missing reports, branch coverage, HTML reports, pyproject settings and a fail-under gate for CI, with…

Read article →
Software Testing

Error Guessing in Testing: Checklist + Demo

Error guessing uses tester experience to predict where code breaks. Get a ready checklist of risky inputs, a step by…

Read article →
Databases & SQL

SQL LAG and LEAD: Compare Rows, 5 Examples

SQL LAG and LEAD read values from the previous or next row without a self join. Five tested examples: change,…

Read article →
Databases & SQL

SQL STRING_AGG: Combine Rows Into One String

SQL STRING_AGG joins values from many rows into one string per group. See syntax for PostgreSQL, SQL Server, MySQL GROUP_CONCAT,…

Read article →
Artificial Intelligence

BM25 Explained: How Keyword Search Ranks Results, With Python Code and Hybrid Search

BM25 explained with a pure Python implementation we ran: the formula, IDF, term saturation, the k1 and b parameters, why…

Read article →
DevOps

Git Bisect Explained: Find the Commit That Broke Your Code, Manually or Automatically

Git bisect explained with a tested repository: find the one bad commit among 41 in 5 test runs, automate it…

Read article →
Test Automation

pytest Markers Explained: Custom Marks, skip, skipif, xfail and -m Filters

pytest markers explained with a tested suite: register custom marks, run only smoke tests with -m, combine filters with and,…

Read article →
Software Testing

Positive vs Negative Testing: Differences, 24 Real Test Cases and a Checklist

Positive vs negative testing explained with a real signup form: 6 positive and 18 negative test cases run in pytest,…

Read article →
Artificial Intelligence

Cosine Similarity Explained: Formula, Worked Example and Python Code

Cosine similarity explained simply: the formula, a worked example by hand, pure Python and NumPy code, cosine vs Euclidean distance…

Read article →
DevOps

Git Squash Commits: 4 Easy Ways, Tested Step by Step (rebase -i, reset, merge)

Git squash commits explained with 4 tested methods: interactive rebase, reset –soft, merge –squash and fixup with autosquash. Before-and-after logs,…

Read article →
Test Automation

pytest parametrize Explained: 7 Patterns with Tested Examples

pytest parametrize explained with 7 tested patterns: basic cases, readable ids, stacked decorators, pytest.param with xfail and skip, indirect fixtures…

Read article →
Software Testing

Retesting vs Regression Testing: 8 Key Differences with a Real Bug Fix Example

Retesting vs regression testing explained with a real bug fix run in pytest: retesting confirmed the fix, the regression run…

Read article →
Artificial Intelligence

RAG Chunking Strategies Explained: Fixed, Overlap, Sentence, Recursive and Headings, Measured

RAG chunking strategies compared on one document with tiktoken 0.14: fixed-size, overlap, sentence packing, recursive splitting and heading-based chunks, measuring…

Read article →
DevOps

Git Stash Explained: Save, Apply, Pop and Untracked Files, Tested

Git stash explained with commands we ran on Git 2.56: push with a message, untracked files, list and show, apply…

Read article →
Test Automation

Test Doubles Explained: Dummy, Stub, Spy, Mock and Fake, with Tested Python Code

Test doubles explained with one Python example run in pytest 9.2: dummy, stub, spy, mock and fake, when to use…

Read article →