jsschools

Edit Distance (Levenshtein)

Computes the minimum number of single-character insertions, deletions, and substitutions required to transform one string into another.

Spec ↗

Syntax

editDistance(a, b)

Parameters

NameTypeRequiredDescription
a string Yes Source string to transform from.
b string Yes Target string to transform to.

Returns

number — Minimum edit distance (Levenshtein distance) between a and b.

Examples

function editDistance(a, b) {
  const m = a.length, n = b.length;
  // Use two rows to save space
  let prev = Array.from({length: n + 1}, (_, j) => j);
  let curr = new Array(n + 1);

  for (let i = 1; i <= m; i++) {
    curr[0] = i;
    for (let j = 1; j <= n; j++) {
      if (a[i-1] === b[j-1]) curr[j] = prev[j-1];
      else curr[j] = 1 + Math.min(prev[j-1], prev[j], curr[j-1]);
    }
    [prev, curr] = [curr, prev];
  }
  return prev[n];
}

console.log(editDistance('kitten', 'sitting'));
console.log(editDistance('sunday', 'saturday'));
Output 
3
3

// Edge cases: empty strings
function editDistance(a, b) {
  const m = a.length, n = b.length;
  let prev = Array.from({length:n+1},(_,j)=>j), curr = new Array(n+1);
  for(let i=1;i<=m;i++){
    curr[0]=i;
    for(let j=1;j<=n;j++) curr[j]=a[i-1]===b[j-1]?prev[j-1]:1+Math.min(prev[j-1],prev[j],curr[j-1]);
    [prev,curr]=[curr,prev];
  }
  return prev[n];
}

console.log(editDistance('', 'abc')); // 3 insertions
console.log(editDistance('abc', '')); // 3 deletions
console.log(editDistance('', ''));    // 0
Output 
3
3
0

Notes

| Case | Time | Space | |---------|-------|-------| | Best | O(mn) | O(n) | | Average | O(mn) | O(mn) | | Worst | O(mn) | O(mn) | The two-row optimisation reduces space from O(mn) to O(n). The standard Levenshtein distance counts insertions, deletions, and substitutions each with cost 1. Damerau-Levenshtein also counts transpositions (swapping adjacent characters). Edit distance underpins spell checkers, DNA sequence alignment, and diff utilities. It relates to LCS: editDist(a, b) = m + n - 2·lcs(a, b) when only insertions and deletions are allowed.

See also