Levenshtein

levenshtein.rb

module Levenshtein
  class << self
    def call(a, b)
      return cache["#{a}-#{b}"] if cache["#{a}-#{b}"]

      cache["#{a}-#{b}"] = cache["#{b}-#{a}"] = -> {
        return a.length if b.length.zero?
        return b.length if a.length.zero?

        a_head, a_tail = a.chars.then { |head, *tail| [head, tail.join] }
        b_head, b_tail = b.chars.then { |head, *tail| [head, tail.join] }

        return call(a_tail, b_tail) if a_head == b_head

        [
          call(a_tail, b),
          call(a, b_tail),
          call(a_tail, b_tail),
        ].min + 1
      }.call
    end

    private

    def cache
      @cache ||= {}
    end
  end
end