Levenshtein

levenshtein.js

const levenshteinDistance = (a, b) => {
  const costs = Array.from({ length: b.length + 1 }, (_, i) => i)

  for (let i = 1; i <= a.length; ++i) {
    costs[0] = i
    let offset = i - 1
    for (let j = 1; j <= b.length; ++j) {
      const arr = [
        costs[j] + 1,
        costs[j - 1] + 1,
        a[i - 1] === b[j - 1] ? offset : offset + 1
      ]
      offset = costs[j]
      costs[j] = Math.min(...arr)
    }
  }

  return costs[b.length]
}

levenshtein.rb

def levenshtein_distance(a, b)
  costs = Array(0..b.length)

  (1..a.length).each do |i|
    costs[0] = i
    offset = i - 1
    (1..b.length).each do |j|
      arr = [
        costs[j] + 1,
        costs[j - 1] + 1,
        a[i - 1] == b[j - 1] ? offset : offset + 1
      ]
      offset = costs[j]
      costs[j] = arr.min
    end
  end

  costs[b.length]
end