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 transposition of adjacent characters as a one-step edit. This calculator implements optimal string alignment, a restricted variant in which a substring cannot be edited more than once. Full Damerau-Levenshtein can produce a different result for some overlapping edits.

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.

Edit distance can help rank spelling candidates, compare OCR output, or find similar identifiers. It is only one signal: names, natural language, source code, and biological sequences often need domain-specific costs or algorithms. Do not treat a low distance as proof that two records identify the same person or item.

This implementation uses O(m x n) dynamic programming, so work grows with the product of the input lengths. The calculator rejects comparisons above one million cells before allocating the table. For larger workloads, use a thresholded, banded, or linear-memory algorithm.