Skip to content
Algorithm Atlas
Pattern MatchingAll categories
CoreSource checked

Levenshtein Distance

Measures how many insertions, deletions, or substitutions transform one string into another.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Pattern Matching
Difficulty
Intermediate
Family
Edit Distance
Tier
Core
Status
Verified
Review
Source Checked
Sources
2
Formulas
1
Relationships
11
Code example
Ready
Visualization
Ready
Aliases
Edit Distance

Overview

Levenshtein Distance uses dynamic programming to compare prefixes of two strings and choose the cheapest edit sequence.

Core Concepts

pattern comparisonstring sequenceedit operation costdynamic programmingedit distancesequence scanpattern statematch verification

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(nm)

Average

O(nm)

Worst

O(nm)

Space

O(nm)

When to Use

  • Use Levenshtein Distance when you need to build an edit-distance table.
  • Use it for spell checking with inputs like two strings.
  • Use it when exact, fuzzy, or structured patterns must be found in sequences.
  • Use it when the Edit Distance tradeoff is acceptable for the problem size.

When Not to Use

  • Avoid it when the state table would exceed available memory.
  • Avoid it when preprocessing cost is larger than a one-off simple scan.
  • Avoid it when the required output is not edit distance.

What It Does

  • Builds an edit-distance table
  • Chooses the cheapest edit at each prefix pair

Use Cases

  • Spell checking
  • Fuzzy search
  • String similarity scoring

Inputs

  • Two strings

Outputs

  • Edit distance
  • Optional edit path

Key Formulas (1)

Edit-distance recurrence

dp[i][j] = min(dp[i−1][j] + 1, dp[i][j−1] + 1, dp[i−1][j−1] + cost)
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost)

Chooses the cheapest insert, delete, or substitute action.

Pseudocode

  1. 1.Create a table for string prefixes
  2. 2.Initialize empty-prefix edit costs
  3. 3.For each pair of characters, compare match, insert, delete, and substitute costs
  4. 4.Store the minimum cost
  5. 5.Return the bottom-right table value

Canonical Example

Input
source = "kitten", target = "sitting"
Output
distance = 3
Explanation
One optimal edit sequence substitutes s for k, substitutes i for e, and inserts g.

Implementation Notes

  • Fill a dynamic-programming table over prefixes of both strings.
  • Use rolling rows when only the final distance is needed.
  • Define costs consistently if substitutions, insertions, and deletions are weighted.

Common Pitfalls

  • Initializing the first row or column incorrectly.
  • Confusing substitution cost with delete-plus-insert cost.
  • Using full O(mn) memory when only the distance is needed.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show a dynamic programming grid filling with edit costs.

Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Create a table for string prefixes
edit-distance-table

Notes

Space can be reduced when only the distance is needed.

Sources (2)

What each reference supports for this entry.

Algorithms on Strings, Trees, and Sequences

Book

String algorithms reference covering Levenshtein Distance recurrences, automata/indexing structures, or exact/approximate matching role.

Levenshtein 1966

Paper

Original reference for edit distance with insertions, deletions, substitutions, and reversals in string correction.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
AlternativesJaro-Winkler Distance

Pattern Matching · Extended

Jaro-Winkler and Levenshtein distance are string similarity measures with different error models.

Compare with this
AlternativesOptimal String Alignment

Pattern Matching · Extended

Optimal string alignment extends Levenshtein-style edit distance with adjacent transpositions under a restricted model.

Compare with this
GeneralizesHamming Distance

Pattern Matching · Core

Levenshtein distance allows insertions and deletions, while Hamming distance assumes equal length.

Compare with this
Conceptual neighborDynamic Time Warping

Pattern Matching · Core

Both use dynamic programming to align sequences.

Compare with this
Conceptual neighborsHirschberg Algorithm

Pattern Matching · Core

Both use dynamic programming ideas for related sequence alignment problems.

Compare with this
Conceptual neighborsSmith-Waterman

Pattern Matching · Core

Both use dynamic programming over edit-like sequence operations.

Compare with this

Relationships

View full relationship page
Conceptual neighborDynamic Time Warping

Both use dynamic programming to align sequences.

GeneralizesHamming Distance

Levenshtein distance allows insertions and deletions, while Hamming distance assumes equal length.

Related Algorithms

Needleman-WunschRegular Expression Matching

Tags

Pattern MatchingStringsEdit DistanceDynamic Programming