Levenshtein Distance, commonly called Edit Distance, measures how different two strings are by calculating the minimum number of editing operations required to transform one string into another.
The standard version allows three operations:
- Insert a character
- Delete a character
- Replace a character
Each operation normally has a cost of 1.
For example:
cat → cut
Only one replacement is required, so:
Levenshtein Distance = 1
A classic example
Consider:
kitten
sitting
One optimal transformation is:
kitten
→ sitten Replace k with s
→ sittin Replace e with i
→ sitting Insert g
Therefore:
Distance = 3
The important word is minimum. There may be many possible edit sequences, but we want the cheapest one.
Why simple positional comparison is not enough
Hamming Distance compares corresponding positions and normally requires equal-length inputs.
Levenshtein Distance also handles insertions and deletions.
For example:
cat
cats
requires only one insertion:
Distance = 1
This makes Edit Distance useful in spell checking, fuzzy search, text normalization, and approximate matching.
Dynamic Programming formulation
For strings a and b, define:
dp[i][j]
as the minimum number of operations required to transform the first i characters of a into the first j characters of b.
Base cases
Transforming an empty string into the first j characters of b requires j insertions:
dp[0][j] = j
Transforming the first i characters of a into an empty string requires i deletions:
dp[i][0] = i
Transition formula
If the current characters match:
a[i - 1] === b[j - 1]
no new edit is required:
dp[i][j] = dp[i - 1][j - 1]
Otherwise we consider three possibilities:
Delete → dp[i - 1][j]
Insert → dp[i][j - 1]
Replace → dp[i - 1][j - 1]
and choose the minimum:
dp[i][j] = 1 + min(
dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1]
)
Example DP table
For:
cat
cut
we obtain:
"" c u t
"" 0 1 2 3
c 1 0 1 2
a 2 1 1 2
t 3 2 2 1
The bottom-right value is 1, which is the final distance.
TypeScript implementation
function levenshteinDistance(a: string, b: string): number {
const rows = a.length + 1;
const cols = b.length + 1;
const dp: number[][] = Array.from(
{ length: rows },
() => new Array(cols).fill(0)
);
for (let i = 0; i < rows; i++) {
dp[i][0] = i;
}
for (let j = 0; j < cols; j++) {
dp[0][j] = j;
}
for (let i = 1; i < rows; i++) {
for (let j = 1; j < cols; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1]
);
}
}
}
return dp[a.length][b.length];
}
Example:
levenshteinDistance("kitten", "sitting"); // 3
Complexity
For strings of lengths n and m:
Time Complexity: O(n × m)
Space Complexity: O(n × m)
The algorithm computes one state for each pair of prefixes.
Space optimization
Each row depends only on the previous row and the current row.
Therefore, the full matrix is not necessary if we only need the final distance.
The memory usage can be reduced to:
O(min(n, m))
Example:
function levenshteinOptimized(a: string, b: string): number {
if (a.length < b.length) {
[a, b] = [b, a];
}
let previous = Array.from(
{ length: b.length + 1 },
(_, i) => i
);
for (let i = 1; i <= a.length; i++) {
const current = new Array(b.length + 1);
current[0] = i;
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
current[j] = previous[j - 1];
} else {
current[j] = 1 + Math.min(
previous[j],
current[j - 1],
previous[j - 1]
);
}
}
previous = current;
}
return previous[b.length];
}
Spell checking
Suppose a user types:
programing
while the dictionary contains:
programming
programmer
processing
The distance to programming is only 1, making it a strong correction candidate.
This is one reason Edit Distance is frequently introduced when discussing spell-check systems.
Fuzzy search
Exact matching can fail when users make small mistakes.
For example:
Stored: Alexander
Query: Alexnder
Levenshtein Distance can quantify how similar the strings are and help rank approximate matches.
This concept is relevant to:
- Search systems
- Contact lookup
- Product search
- CRM systems
- Record matching
Data cleaning and deduplication
Consider two CRM records:
Arian Soleimanzadeh
Arian Soleimanzade
A small Edit Distance may be evidence that the records represent the same person.
In production systems, however, names alone should not determine duplication. Email addresses, phone numbers, identifiers, and other fields should also be considered.
NLP and OCR
Edit Distance can support tasks such as:
- Typo detection
- Text normalization
- OCR correction
- Transliteration matching
- Approximate token matching
For OCR, for example, a scanned word may contain a few incorrect characters. Edit Distance helps compare the recognized output with dictionary candidates.
Bioinformatics
DNA sequences can also be treated as character sequences.
For example:
ACGTAC
ACGTC
Edit-distance concepts can describe how one sequence differs from another, although real bioinformatics applications often use more specialized alignment algorithms and cost models.
Levenshtein vs. Hamming Distance
Hamming Distance compares corresponding positions and generally assumes equal lengths.
Levenshtein allows insertion and deletion as well as replacement.
For:
cat
cut
both return 1.
But for:
cat
cats
standard Hamming Distance is not suitable, while Levenshtein Distance is 1.
Levenshtein vs. LCS
Levenshtein Distance and Longest Common Subsequence are both classic dynamic-programming problems, but they answer different questions.
Levenshtein asks:
What is the minimum number of edits?
LCS asks:
What is the longest subsequence shared by both sequences?
Recognizing this difference is useful in technical interviews.
Weighted Edit Distance
The three operations do not always need to have equal cost.
A system might define:
Insert = 1
Delete = 1
Replace = 2
Or a keyboard-aware spelling system might assign a lower replacement cost to neighboring keys.
These variations are generally known as Weighted Edit Distance.
Common interview problem
A standard question asks:
Given
word1andword2, find the minimum number of insertions, deletions, and replacements needed to transform one into the other.
Example:
word1 = horse
word2 = ros
The answer is:
3
This is one of the classic examples used to teach Dynamic Programming.
Why a simple greedy approach is risky
Choosing the apparently best edit at each mismatch does not guarantee the globally optimal transformation.
An insertion or deletion changes the alignment of all characters that follow.
Dynamic Programming handles this by evaluating and reusing solutions to smaller prefix problems.
Common implementation mistakes
Off-by-one indexing
Because row zero represents the empty string, DP index i usually refers to character:
a[i - 1]
Incorrect initialization
The first row and column must represent the cost of transforming to or from an empty string.
Charging for equal characters
If characters match, no extra cost is added.
Confusing neighboring states
A useful mental model is:
up → delete
left → insert
diagonal → replace
When not to run Levenshtein against everything
Comparing one query against millions of database records using full Edit Distance can be computationally expensive.
Real search systems often reduce candidates first using techniques such as:
- Indexes
- Prefix filtering
- N-grams
- Trigrams
- Search engines
and then apply more expensive similarity calculations to a smaller candidate set.
Conclusion
Levenshtein Distance calculates the minimum number of insertions, deletions, and replacements required to transform one string into another.
The standard dynamic-programming solution has:
Time: O(n × m)
Space: O(n × m)
with memory optimization possible down to:
O(min(n, m))
Beyond algorithm exercises, Edit Distance is directly relevant to spell checking, fuzzy search, CRM deduplication, data cleaning, NLP, OCR, and approximate string matching.