String distance (Levenshtein) in ES6 Javascript

One of the cooler and lesser used algorithms I learn in my time at my university was the Levenstshtein distance algorithm. You see it in action almost every time you use search and you get suggested results back. A lot of time, these suggestions are just coming from the backend, so a web developer isn't really exposed to how they work.

It's a fairly straightforward algorithm to implement with recursion. Basically, it is just iterating over a string and checking for the path of least resistance to get to the other string. It's useful anytime you need to deal with user input that could be wrong and still have meaningful results displayed.

const distance = (string1, string2) => {  
  if (!string1 || string1.length === 0) {
    return string2.length;
  }
  if (!string2 || string2.length === 0) {
    return string1.length;
  }
  let [head1, ...tail1] = string1;
  let [head2, ...tail2] = string2;
  if (head1 === head2) {
    return distance(tail1, tail2);
  }
  const l1 = distance(string1, tail2);
  const l2 = distance(tail1, string2);
  const l3 = distance(tail1, tail2);
  return 1 + Math.min(l1, l2, l3);
}

On a side note, this implementation always works as well for arrays of any data, not just strings. For example you could call it with distance([1,2,3], [1,3]).

See it in action with JSFiddle.

Bret Lowrey

Code is like a war - the best code is one never written.

Florida, USA