string/levenshtein

What it does

Measures how far apart two strings are in JavaScript and TypeScript, as the smallest number of single-character edits - insert one character, delete one, replace one - that turns the first into the second. It is the classic edit distance and nothing else: a transposition costs two edits rather than one, every edit costs the same, and the result is a count rather than a similarity score between zero and one. The decision that separates implementations of it is invisible in the signature and is settled here: an edit is one Unicode code point, so a string holding one emoji is one edit away from the empty string. The widely used JavaScript implementations count UTF-16 code units instead and answer two, because JavaScript strings are stored as UTF-16 and an emoji occupies two of them. Nothing is normalised, nothing is folded to lower case and nothing is trimmed, so two strings that a person would call the same and a computer would not are one or more edits apart - which is what a caller who wants otherwise applies before calling. The result is always a non-negative whole number, and the function is a metric: zero exactly on two identical strings, the same in both directions, and never improved by a detour through a third string.

The language ships no edit distance, and nothing in Intl measures the gap between two strings.

Human-authored text held in memory: names, labels, search queries, product codes, identifiers, and short free text. Typo tolerance, deduplication, "did you mean", and the suggestion of a nearest match from a small set. It is not a similarity ratio, not a phonetic match, not a locale-aware comparison, and not an index: a caller ranking one query against a large corpus wants a data structure, and this function is what such a structure would call. Damerau-Levenshtein, where a transposition costs one edit, and weighted edit distances, where the operations cost different amounts, answer different questions and are separate contracts.

Signature

type Levenshtein = (a: string, b: string) => number

// typescript/string/levenshtein@1 - https://toopo.dev/typescript/string/levenshtein@1/
// Copyright (c) 2026 Mathis Perron. SPDX-License-Identifier: MIT-0

/**
 * `string/levenshtein@1` - count the single-character insertions, deletions and substitutions that
 * turn one string into the other.
 *
 * Written to be read: correctness and obviousness come before speed. The whole matrix is kept rather
 * than the two rows the recurrence needs, so that the code can be read against the definition it
 * implements. The two-row and banded variants compute the same numbers in less memory; under this
 * contract they are competing implementations, and this one is the oracle they are compared against.
 *
 * The unit is the Unicode code point - what `for...of` and `Array.from` yield, and what the contract
 * argues for at length. What matters here is that the same decomposition is applied to both
 * arguments and that nothing else touches them: the axioms this function claims only hold if the two
 * sides are measured in one unit, and an implementation that counted one side in code points and
 * normalised the other would break the triangle inequality without ever answering an obviously wrong
 * number.
 *
 * There is no diagnostic export beside this one. Every pair of strings has a distance, so there is no
 * refusal to describe.
 */
export const levenshtein = (a: string, b: string): number => {
  const left = [...a]
  const right = [...b]

  /**
   * `distance[i][j]` is the distance between the first `i` code points of `left` and the first `j`
   * of `right`.
   */
  const distance: number[][] = []

  // The two trivial edges of the matrix: turning a prefix into the empty string costs one deletion
  // per code point, and turning the empty string into a prefix costs one insertion per code point.
  for (let i = 0; i <= left.length; i += 1) {
    distance[i] = new Array<number>(right.length + 1)
    distance[i][0] = i
  }

  for (let j = 0; j <= right.length; j += 1) distance[0][j] = j

  for (let i = 1; i <= left.length; i += 1) {
    for (let j = 1; j <= right.length; j += 1) {
      const substitution = distance[i - 1][j - 1] + (left[i - 1] === right[j - 1] ? 0 : 1)
      const deletion = distance[i - 1][j] + 1
      const insertion = distance[i][j - 1] + 1

      distance[i][j] = Math.min(substitution, deletion, insertion)
    }
  }

  return distance[left.length][right.length]
}

Try it on your own input

This calls levenshtein on whatever you type. What you type into a field is the value, character for character, and the form opens on identical-text so there is a call that works to edit. What comes back is what the function answered, under the call it was made from — invisible characters are named there, so two inputs that look alike on screen do not print alike.

The JavaScript this runs is string/levenshtein's own reference.ts with its types stripped. That is neither the file the registry serves nor the file its digest covers: both are TypeScript, and no browser runs TypeScript. It is also the only part of this page that needs JavaScript at all.