Levenshtein Distance Calculator
This example calculates the Levenshtein distance from String Tools, pre-loaded with the classic “kitten” to “sitting” comparison. Enter two strings and see the minimum number of single-character edits required to transform one into the other.
How It Works
The Levenshtein distance uses dynamic programming. A matrix is built where each cell represents the edit distance between substrings. The algorithm fills the matrix by considering three operations at each position:
| Operation | Description | Cost |
|---|---|---|
| Insert | Add a character | 1 |
| Delete | Remove a character | 1 |
| Substitute | Replace a character | 1 (if different) |
The final value in the bottom-right cell of the matrix is the Levenshtein distance.
The “kitten” to “sitting” Example
The classic example requires 3 edits:
- kitten → sitten (substitute k with s)
- sitten → sittin (substitute e with i)
- sittin → sitting (insert g at the end)
Distance = 3.
Time and Space Complexity
The algorithm runs in O(m x n) time and space, where m and n are the lengths of the two strings. For most practical text comparisons (under 1000 characters), this executes instantly in the browser.
Variations
Several algorithms modify Levenshtein for specific use cases:
- Damerau-Levenshtein adds transposition (swapping adjacent characters) as a fourth operation
- Weighted Levenshtein assigns different costs to operations (e.g., substitution costs more than insertion)
- ** restricted edit distance** limits which operations are allowed
How to Use
- Enter the first string in the input field
- Enter the second string in the second field
- The edit distance appears in the result area
- The tool also shows the step-by-step transformation
Common Questions
What is the maximum possible distance?
The maximum distance is the length of the longer string, which happens when one string is entirely empty and you must insert every character. For two strings of lengths m and n, the distance is at most max(m, n).
How does case sensitivity affect the result?
Comparison is case-sensitive. Hello and hello have a distance of 1 (the H/h difference). For case-insensitive comparison, convert both strings to lowercase first.
Can I use this for DNA sequence comparison?
Yes. Levenshtein distance is commonly used in bioinformatics to measure similarity between DNA or protein sequences. Each character represents a nucleotide or amino acid, and the edit distance reflects the number of mutations between sequences.