Levenshtein and Damerau distance in JavaScript, step by step

Under the hood · Published 2026-10-06

Edit distance answers a simple question: how many single-character changes does it take to turn one word into another? It is the backbone of spelling suggestions, fuzzy search and "did you mean" features.

The definition

The Levenshtein distance between two strings is the minimum number of insertions, deletions and substitutions of single characters needed to transform one into the other. It is named after Vladimir Levenshtein, who described it in a 1965 paper on error-correcting codes. The textbook example: kitten → sitting has distance 3 (substitute k→s, substitute e→i, insert g).

Two properties make it useful. It is a true metric (distance zero only for identical strings, symmetric, and obeying the triangle inequality), so it behaves sensibly in search structures. And it can be computed exactly with a short dynamic-programming algorithm, usually credited to Wagner and Fischer (1974), in time proportional to the product of the two lengths.

The dynamic-programming table

Build a table d with one row per character of a (plus one) and one column per character of b (plus one). Cell d[i][j] holds the distance between the first i characters of a and the first j characters of b. The first row and column are easy: turning a prefix into the empty string takes as many deletions as it has characters. Every other cell takes the cheapest of three moves:

• from the cell above, plus one: delete a character of a;
• from the cell to the left, plus one: insert a character of b;
• from the diagonal, plus zero if the two characters match or one if they differ: keep or substitute.

The answer is in the bottom-right cell.

function levenshtein(a, b) {
  const m = a.length, n = b.length;
  const d = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) d[i][0] = i;
  for (let j = 0; j <= n; j++) d[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1;
      d[i][j] = Math.min(
        d[i - 1][j] + 1,        // deletion
        d[i][j - 1] + 1,        // insertion
        d[i - 1][j - 1] + cost  // substitution or match
      );
    }
  }
  return d[m][n];
}

levenshtein('kitten', 'sitting');  // 3
levenshtein('recieve', 'receive'); // 2

Here is the filled table for cat → cart. Read the bottom-right value: one insertion.

Adding transpositions (Damerau)

Notice that recieve → receive scored 2: plain Levenshtein sees a swap of ie as two substitutions. Fred Damerau's 1964 study of spelling errors found that transposed adjacent letters are one of the four most common single errors, alongside insertion, deletion and substitution, so spell checkers usually count a swap as one edit. The common way to add that is one extra case in the loop:

function osaDistance(a, b) {
  const m = a.length, n = b.length;
  const d = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) d[i][0] = i;
  for (let j = 0; j <= n; j++) d[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1;
      d[i][j] = Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
      if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) {
        d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + 1); // transposition
      }
    }
  }
  return d[m][n];
}

osaDistance('recieve', 'receive'); // 1

Strictly speaking, this computes the optimal string alignment (OSA) distance, a restricted form of Damerau–Levenshtein in which no substring may be edited twice. The difference shows in odd cases: OSA gives ca → abc a distance of 3, while the unrestricted Damerau–Levenshtein distance is 2 (swap to ac, then insert b). OSA is also not a true metric, because it can violate the triangle inequality. For spelling suggestions this almost never matters, and OSA is what most libraries mean by "Damerau distance". If you need the unrestricted version, it requires an extra table of last-seen positions per character; the Wikipedia article on Damerau–Levenshtein distance gives both algorithms.

Saving memory and time

Each row of the table only depends on the previous row, so you can keep two rows instead of the full matrix. And if you only care whether the distance is at most some threshold, as a spell checker does, you can stop as soon as every value in a row exceeds it:

function levenshteinWithin(a, b, max = Infinity) {
  if (a.length < b.length) [a, b] = [b, a];     // b is the shorter string
  if (a.length - b.length > max) return max + 1; // length gap alone is too big
  let prev = Array.from({ length: b.length + 1 }, (_, j) => j);
  let cur = new Array(b.length + 1);
  for (let i = 1; i <= a.length; i++) {
    cur[0] = i;
    let rowMin = cur[0];
    for (let j = 1; j <= b.length; j++) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1;
      cur[j] = Math.min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + cost);
      if (cur[j] < rowMin) rowMin = cur[j];
    }
    if (rowMin > max) return max + 1;            // cannot get back under the limit
    [prev, cur] = [cur, prev];
  }
  return prev[b.length];
}

levenshteinWithin('kitten', 'sitting', 1); // 2, meaning "more than 1"

Memory drops from m×n to about n numbers, and the early exit skips most of the work when comparing a word against thousands of clearly different dictionary entries.

Using it for suggestions

The straightforward use is to compare a misspelled word with every word in a list and keep the closest:

function closest(word, list, max = 2) {
  return list
    .map(w => [w, osaDistance(word, w)])
    .filter(([, dist]) => dist <= max)
    .sort((x, y) => x[1] - y[1] || x[0].localeCompare(y[0]))
    .slice(0, 5);
}

closest('acress', ['actress', 'across', 'acres', 'access', 'caress', 'address']);
// all five of actress, across, acres, access, caress are at distance 1

That example shows the limit of distance alone: five candidates tie. Ranking them needs extra information, usually word frequency and the likelihood of each particular error; how spell checkers work covers the noisy channel model behind that. It also shows the cost: comparing against a 70,000-word list means 70,000 table computations per word. For that reason the Letterbench checker does the reverse, generating all strings within one or two edits and looking each one up in a Set, as explained in its documentation. For very large dictionaries, structures such as BK-trees (which exploit the triangle inequality) or the symmetric-delete method are faster still.

Unicode caveat

JavaScript strings are sequences of UTF-16 code units, so a[i] splits characters outside the Basic Multilingual Plane, such as emoji, into two halves, and an accented letter may be one code point (é) or two (e plus a combining accent). For general text, normalize first with str.normalize('NFC') and iterate with Array.from(str), which splits by code point. For plain English words neither issue arises.