Levenshtein Distance Calculator

Calculate the edit distance between two strings using insertions, deletions, and substitutions. Visualize the optimal alignment and transformation steps.

String Input & Configuration

Length: 0

Length: 0

Quick Examples:

String Alignment Preview

Enter strings to see alignment
Enter strings to see alignment
Operations will be shown here

Distance Visualization

About Levenshtein Distance

What is Levenshtein Distance?

The Levenshtein distance, also known as edit distance, is the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one string into another. Unlike Hamming distance, it works with strings of different lengths and provides a more flexible measure of string similarity.

Algorithm Variants

Standard Levenshtein

Uses insertions, deletions, and substitutions with equal cost (typically 1).

Weighted Edit Distance

Allows different costs for different operations based on application needs.

Damerau-Levenshtein

Includes transpositions (swapping adjacent characters) as a fourth operation.

Applications

Spell Checking

Find the closest correctly spelled words to a misspelled input.

DNA Sequence Analysis

Compare genetic sequences and identify mutations or variations.

Fuzzy String Matching

Find approximate matches in databases and search systems.

Version Control

Calculate differences between file versions in Git and other VCS.

Natural Language Processing

Measure text similarity and perform approximate text matching.

Data Deduplication

Identify and merge similar records in databases.

Algorithm Complexity

  • Time Complexity: O(m × n) where m and n are string lengths
  • Space Complexity: O(m × n) for full matrix, O(min(m,n)) with optimization
  • Dynamic Programming: Uses optimal substructure and overlapping subproblems
  • Optimization: Can be optimized to use only O(min(m,n)) space

How to Use This Calculator

  1. Choose the algorithm type (Standard, Weighted, or Damerau-Levenshtein)
  2. Set operation costs if using weighted edit distance
  3. Configure case sensitivity as needed
  4. Enter the two strings you want to compare
  5. Click "Calculate Edit Distance" to analyze
  6. Review the alignment, transformation steps, and DP matrix
  7. Export results for documentation or further analysis

Example Calculations

Word Similarity:
"kitten" → "sitting"
Distance: 3 (substitute k→s, substitute e→i, insert g)
Typo Correction:
"recieve" → "receive"
Distance: 2 (transpose ie→ei)
DNA Mutation:
"ATCG" → "AGTCG"
Distance: 1 (insert G at position 2)

Comparison with Other Metrics

  • vs Hamming Distance: Works with different length strings, allows insertions/deletions
  • vs Jaro-Winkler: More intuitive for character-level edits, better for short strings
  • vs Cosine Similarity: Character-based rather than token-based, preserves order
  • vs Longest Common Subsequence: Counts all operations, not just matches