Levenshtein Distance Calculator
Inputs
| First string | kitten |
|---|---|
| Second string | sitting |
Levenshtein Distance Calculator
Compute the Levenshtein (edit) distance between two strings — the minimum number of single-character insertions, deletions, and substitutions needed to turn one into the other — along with a similarity percentage.
Inputs
Strings
Results
Enter a value to see results.
Results
Levenshtein Distance
Levenshtein distance, also called edit distance, measures how different two strings are by counting the smallest number of single-character edits needed to turn one into the other. The allowed edits are insertion, deletion, and substitution, each costing one. The calculator takes two strings and returns that distance together with a similarity percentage, making it useful for spell-checking, fuzzy matching, and comparing sequences such as DNA.
The three edit operations
Every transformation between two strings can be expressed as a sequence of three basic moves. An insertion adds one character, a deletion removes one, and a substitution replaces one character with another. Levenshtein distance asks for the cheapest such sequence, where every move costs one. Because substitution is a single step rather than a delete followed by an insert, changing one letter is always counted as one edit, not two.
Named after Vladimir Levenshtein, who defined it in a 1965 paper, the measure generalizes the older Hamming Distance Calculator: Hamming distance allows only substitutions and only for strings of equal length, while Levenshtein distance also permits insertions and deletions, so it handles strings whose lengths differ.
The dynamic-programming table
The distance is computed by filling a table with one row per character of the first string (plus a leading empty row) and one column per character of the second (plus a leading empty column). Cell holds the edit distance between the first characters of string A and the first characters of string B.
The first row and column count edits against the empty string, so and . Every other cell is the minimum of three candidates:
D[i][j]=min⎩⎨⎧D[i−1][j]+1D[i][j−1]+1D[i−1][j−1]+c(deletion)(insertion)(substitution)where the substitution cost is 0 when the characters match and 1 when they differ. The answer sits in the bottom-right cell. Filling the table takes time proportional to the product of the two lengths, .
Worked example
Take the classic pair "kitten" and "sitting". Reading the optimal path through the table gives three edits:
kittensittensittin→sitten→sittin→sitting(substitute k→s)(substitute e→i)(insert g)No shorter sequence exists, so the distance is 3. The longer string has 7 characters, so the similarity is , or about 57%.
Similarity and its limits
The calculator normalizes the raw distance into a similarity score using
Dividing by the length of the longer string keeps the result between 0% for completely different strings and 100% for identical ones; two empty strings are treated as identical. This is one common normalization — other tools divide by the sum of the lengths or use ratio-based measures — so similarity numbers from different sources are not directly comparable.
Where it is used
Spell-checkers rank candidate corrections by edit distance from the misspelled word. Search and database systems use it for fuzzy matching, tolerating typos when looking up names or addresses. In bioinformatics, edit distance underlies sequence alignment for comparing DNA, RNA, and proteins, where insertions and deletions correspond to mutations. The plain Levenshtein cost model treats all edits equally; applications that need different penalties for different operations, or that must align very long sequences efficiently, extend it with weighted costs or specialized alignment algorithms.
Frequently Asked Questions (FAQ)
What is Levenshtein distance?
Levenshtein distance, also called edit distance, is the minimum number of single-character edits — insertions, deletions, or substitutions — needed to change one string into another. It was introduced by the Soviet mathematician Vladimir Levenshtein in 1965.
For example, the distance between "kitten" and "sitting" is 3: substitute k→s, substitute e→i, and insert g at the end. No shorter sequence of edits exists, so the distance is exactly 3.
The value is computed with a dynamic-programming table whose cells each hold the edit distance between prefixes of the two strings. Building the table takes time proportional to the product of the two lengths.
How is it different from Hamming distance?
Hamming distance counts only substitutions and is defined only for strings of equal length — it compares characters position by position. Levenshtein distance also allows insertions and deletions, so it works for strings of different lengths and captures shifts in alignment.
For two strings of the same length, the Levenshtein distance is always less than or equal to the Hamming distance, because substitution is one of the operations it can use but it may find a cheaper path using insertions and deletions.
How is the similarity percentage calculated?
Similarity is reported as 1 − distance / max(len_a, len_b), expressed as a percentage. Dividing by the length of the longer string normalizes the score to the range from 0% (completely different) to 100% (identical). When both strings are empty, the similarity is defined as 100%.
This is one common normalization; other tools may divide by the sum of the lengths or use ratio-based measures, so similarity scores are not directly comparable across different definitions.