Calculate edit distance
Enter any two strings. Unlike Hamming distance, edit distance supports strings of different lengths.
Example edit distances
kitten → sitting
Distance: 3
Two substitutions and one insertion are sufficient.
flaw → lawn
Distance: 2
One deletion and one substitution can transform the strings.
Saturday → Sunday
Distance: 3
A minimum-cost sequence uses three edits.
→ cat
Distance: 3
Three insertions are required to create the target.
What is edit distance?
Edit distance measures the minimum cost of transforming one sequence into another using a defined set of editing operations. This calculator implements the standard Levenshtein distance, where insertion, deletion, and substitution each cost one.
Dynamic programming formula
Let D[i][j] represent the minimum edit distance between the first i characters of the source and the first j characters of the target.
D[0][j] = j
D[i][j] = min(
D[i-1][j] + 1, deletion
D[i][j-1] + 1, insertion
D[i-1][j-1] + cost match/substitution
)
cost = 0 if source[i] = target[j], otherwise 1
The algorithm fills the matrix from smaller prefixes to larger prefixes. Its bottom-right cell contains the minimum edit distance. Tracing backward through the matrix reconstructs one optimal edit script.
Hamming distance vs. edit distance
Hamming distance counts mismatched positions and requires equal-length strings. Levenshtein edit distance permits insertions and deletions, so it can compare strings of different lengths.
Time and memory
The standard dynamic programming algorithm uses O(m × n) time and memory for strings of lengths m and n. This tool limits the matrix to 40,000 cells to remain practical on typical shared hosting.
Frequently asked questions
What is the difference between edit distance and Levenshtein distance?
Edit distance is a general concept whose exact meaning depends on the allowed operations and their costs. Levenshtein distance is a common version that allows insertions, deletions, and substitutions at unit cost.
Can the two strings have different lengths?
Yes. Insertions and deletions allow the calculator to compare strings of different lengths, including an empty string and a non-empty string.
Is the edit script always unique?
No. Several sequences of operations can produce the same minimum cost. The calculator displays one optimal sequence.
What does 100% similarity mean?
The normalized similarity used here is 100 × (1 − distance / maximum string length). A result of 100% means the compared strings are identical under the selected case setting. Both empty strings are treated as 100% similar.
Does this calculator support Unicode?
If PHP's mbstring extension is installed, the calculator compares Unicode characters. Without it, the fallback compares bytes, which may not match user-perceived characters for non-ASCII text.
Does it count swapping two adjacent letters as one edit?
No. Standard Levenshtein distance does not treat transposition as a single operation. Damerau–Levenshtein distance is a related measure that can account for adjacent character transpositions.