Levenshtein Distance Calculator

Levenshtein distance is the minimum number of single-character insertions, deletions, or substitutions needed to turn one string into another. It was published in 1965 by Soviet mathematician Vladimir Levenshtein in a paper on binary codes capable of correcting deletions, insertions, and reversals. The name stuck even though the same metric had been discovered a few times before; today it underpins spell checkers, fuzzy search, diff tools, and DNA alignment scoring.

Damerau-Levenshtein adds a fourth edit, the transposition of two adjacent characters, and counts it as a single operation instead of two substitutions. Frederic Damerau introduced the variant in 1964 specifically for typo correction because adjacent-key swaps like 'teh' for 'the' are one of the most common keystroke errors. The calculator implements the optimal string alignment variant, the version used by virtually every spell checker, fuzzy finder, and search engine.

Hamming distance counts the positions where two equal-length strings differ, nothing more. Richard Hamming defined it in 1950 for error-detecting and error-correcting codes, where every codeword has a fixed bit length, so 'equal length' is built into the problem. The calculator returns an error rather than padding shorter input because padding would silently change the answer; if you need to compare strings of different length, switch to Levenshtein or Damerau-Levenshtein.

Spell check and autocorrect are the classic case: rank candidate words by their distance to the misspelling and surface the closest few. Fuzzy search (Algolia, ripgrep --fuzzy, IDE symbol jumpers) ranks results by distance to the query. Record linkage in databases finds 'John Smith' and 'Jon Smyth' as likely duplicates. Bioinformatics tools use weighted Levenshtein for DNA and protein sequence alignment. Plagiarism detection, OCR post-processing, and revision-history diffs all rely on the same primitive.

The Wagner-Fischer dynamic-programming table is O(m * n) in both time and memory, where m and n are the two string lengths. For two 100-character strings that is 10,000 cells, computed in microseconds. For two 5,000-character strings (the calculator's cap) you are looking at 25 million cells, which still finishes in well under a second but is the reason the cap exists. If you need to compare megabytes of text, switch to a streaming diff (Myers, patience) or a banded Levenshtein that bails early once distance exceeds a threshold.