Levenshtein distance

levensthein_distance.js

'use strict'

const levenshtein = (a, b) => {
  if (a.length == 0) return b.length
  if (b.length == 0) return a.length
  // swap to save some memory O(min(a,b)) instead of O(a)
  if (a.length > b.length)
    b = [a, a = b][0]
  let row = []
  for (let i = 0 ; i <= a.length ; ++i)
    row[i] = i
  for (let i = 1 ; i <= b.length ; ++i)
  {
    let prev = i
    for (let j = 1 ; j <= a.length ; ++j) {
      let val
      if (b.charAt(i - 1) == a.charAt(j - 1))
        val = row[j - 1] // match
      else
        val = Math.min(row[j - 1] + 1, // substitution
                       prev + 1,     // insertion
                       row[j] + 1)  // deletion
      row[j - 1] = prev
      prev = val
    }
    row[a.length] = prev
  }
  return row[a.length]
}

const _levenshtein = (a, b) => {
  if ((typeof a === 'string' || a instanceof String) &&
    (typeof b === 'string' || b instanceof String))
    console.log("leventshtein(" + a + "," + b + ") = " + levenshtein(a, b))
  else
    console.log("a and/or b is/are not a string")
}

_levenshtein("", "")
_levenshtein(13, 37)
_levenshtein("aaa", "aaa")
_levenshtein("aa", "aaa")
_levenshtein("aa", "aba")
_levenshtein("aaa", "aba")
_levenshtein("0123456789", "aba")
_levenshtein("0123456789", "9876543210")