Skip to content
uencoder

Levenshtein Distance

The Levenshtein distance is the minimum number of single-character insertions, deletions, and substitutions needed to make two strings identical.

Purpose

Measures the edit difference between strings, used for fuzzy matching and spelling correction.

Mechanism

Dynamic programming: d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+cost), where cost is 0 if the characters match and 1 otherwise. Time and space are O(m×n); space can be optimized to O(min(m,n)).

Use cases

  • Spell checking and correction
  • DNA sequence alignment
  • Fuzzy search and deduplication
  • Natural language processing

Examples

  • Input 
    kitten → sitting
    Output 
    3

    Substitute k→s, e→i, and insert g

Common errors

Full O(mn) computation is too slow for long strings
Use a BK-tree or early termination by threshold

Related terms

Hamming Distance
The Hamming distance is the number of positions at which corresponding characters differ between two equal-length strings; it only applies to equal-length comparisons.
GLOSSARY
Jaro-Winkler Distance
The Jaro-Winkler distance is a refinement of the Jaro distance that weights common prefixes, making it better suited for matching short strings such as person names where prefixes matter.
GLOSSARY
Edit Distance
Edit distance is the minimum number of single-character edit operations (insertion, deletion, substitution) required to transform one string into another; the Levenshtein distance is its most common form.
GLOSSARY
Fuzzy Search
Fuzzy search is a search technique tolerant of spelling variations, matching approximate results based on edit distance, n-grams, or phonetic algorithms.
GLOSSARY

Related tools

Hamming Distance
Hamming Distance — pure client-side tool. Privacy-first, no server round-trip.
TOOL

References