levenshtein.rb

  class Levenshtein
    def initialize(words)
      @trie = TrieNode.new
      words.each do |word|
        @trie.insert(word)
      end
    end

    def best_match word
      "Batman"
    end

    def search word, maximum_distance
      current_row = (word.length..(word.length + 1)).to_a
      results = []
      @trie.children.keys.each do |letter|
        search_recursive(@trie.children[letter], letter, word, current_row, results, maximum_distance)
      end
      results
    end

    def search_recursive node, letter, word, previous_row, results, maximum_distance
      columns = word.length + 1
      current_row = [previous_row.first + 1]

      (1...columns).each do |column|
        #fails on the third execution
        insert_cost = current_row[column - 1] + 1
        delete_cost = previous_row[column] + 1

        if word[column - 1] != letter
          replace_cost = previous_row[column - 1] + 1
        else
          replace_cost = previous_row[column - 1]
        end

        current_row << [insert_cost, delete_cost, replace_cost].min
      end

      if current_row.last <= maximum_distance && node.word
        results << {node.word => current_row.last}
      end

      if current_row.min <= maximum_distance
        node.children.keys.each do |letter|
          search_recursive(node.children[letter], letter, word, current_row, results, maximum_distance)
        end
      end
    end
  end

  class TrieNode
    attr_accessor :word, :children

    def initialize
      @children = {}
    end

    def insert word
      node = self
      word.each_char do |letter|
        unless node.children[letter]
          node.children[letter] = TrieNode.new
        end
        node = node.children[letter]
      end
      node.word = word
    end
  end