Levenshtein Distance Calculator

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:

1. kitten → sitten (substitute k with s)
2. sitten → sittin (substitute e with i)
3. 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

1. Enter the first string in the input field
2. Enter the second string in the second field
3. The edit distance appears in the result area
4. 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.