t9.rb

require 'set'

module Trie
  class T9
    attr_reader :root

    def initialize
      @root = Hash.new
    end

    def build(word = '') 
      node = root
      t9numbers = word.tr('a-z', '22233344455566677778889999')
      t9numbers.each_char do |ch|
        node[ch] ||= Hash.new
        node = node[ch]
      end
      node['end'] ||= Set.new
      node['end'].add(word)
    end

    def find(t9numbers = '') 
      node = root
      t9numbers.each_char do |ch|
        return [] unless node = node[ch]
      end
      node['end'].to_a
    end
  end
end

trie = Trie::T9.new
trie.build('foo')
trie.build('bar')
trie.build('foo')
trie.build('fom')
trie.find('366')