Levenshtein Distance Calculator

The calculator uses the Wagner–Fischer dynamic-programming algorithm, the standard method for computing the Levenshtein (edit) distance defined by Vladimir Levenshtein in 1966. Given two strings A of length m and B of length n, it fills a table of size (m+1) × (n+1) where each cell d[i][j] holds the edit distance between the first i characters of A and the first j characters of B.

1. Apply the pre-processing toggles first: lowercase both strings if the comparison is case-insensitive, and strip whitespace if that option is on.
2. Initialise the edges: d[i][0] = i (turning a prefix into an empty string costs i deletions) and d[0][j] = j (building from empty costs j insertions).
3. Fill each remaining cell with the recurrence below, where the substitution cost is 0 when the characters match and 1 when they differ:

   cost = (A[i-1] == B[j-1]) ? 0 : 1
   d[i][j] = min(
     d[i-1][j]   + 1,   // deletion
     d[i][j-1]   + 1,   // insertion
     d[i-1][j-1] + cost // substitution / match
   )

4. The Levenshtein distance is the bottom-right cell, d[m][n].
5. Backtrack from d[m][n] to d[0][0], at each step choosing the predecessor that produced the minimum, to recover one optimal edit script and the per-operation counts. Ties are broken in a fixed, documented order: match, substitution, deletion, insertion.

The algorithm runs in O(m × n) time. The similarity percentage shown alongside the distance is a presentation convenience, computed as (1 − distance / max(m, n)) × 100 and defined as 100% when both strings are empty; it is not part of the formal Levenshtein definition. Every result is independently cross-checked against a second, space-optimized two-row implementation of the same recurrence — if the two ever disagreed, the badge in the tool would flag it.

• Levenshtein, V. I. (1966) — Binary codes capable of correcting deletions, insertions and reversals (Soviet Physics Doklady)
• Wagner, R. A. & Fischer, M. J. (1974) — The String-to-String Correction Problem (Journal of the ACM)
• NIST Dictionary of Algorithms and Data Structures — Levenshtein distance

The algorithm, recurrence, and worked examples on this page were last cross-checked against these sources on 2026-06-10. The distance is deterministic and verified against an independent second implementation on every calculation.