trie.rb

class Trie

  def initialize
    @root = {}
  end

  def build(string)
    node = @root
    string.chars.each do |char|
      node[char] ||= {}
      node = node[char]
    end
    node[:end] = true
  end

  def build2(string, node = @root)
    node[:end] = true and return if string.size == 0
    char = string[0]
    node[char] ||= {}
    node = node[char]
    build2(string[1..-1], node)
  end

  def include?(word, node = @root)
    return false if node.nil?
    return true if node[:end] and word == ""
    include?(word[1..-1], node[chars[0]])
  end

  def prefixed(prefix, node = @root)
    prefix.chars.each do |char|
      return unless node[char]
      node = node[char]
    end

    to_a(node).map { |suffix| prefix + suffix }
  end

  def prefixed2(prefix, chars = prefix, node = @root)
    if node[chars[0]]
      node = prefixed2(prefix, chars[1..-1], node[chars[0]])
    elsif chars == ""
      return to_a(node).map { |suffix| prefix + suffix }
    else
      return []
    end
  end

  def to_a(node = @root, prefix = "", array = [])
    node.each do |key, value|
      case key
      when :end
        array << prefix
      else
        to_a(value, prefix + key, array)
      end
    end
    array
  end

end