Commit 4b1893e

@@ -0,0 +1,109 @@
+#!/usr/bin/env ruby
+
+def assert_equal(expected, actual)
+  raise "expected: #{expected.inspect}, actual: #{actual.inspect}" unless expected == actual
+end
+
+LETTER_DIGIT_MAPPING = {
+  'a' => 2,
+  'b' => 2,
+  'c' => 2,
+  'd' => 3,
+  'e' => 3,
+  'f' => 3,
+  'g' => 4,
+  'h' => 4,
+  'i' => 4,
+  'j' => 5,
+  'k' => 5,
+  'l' => 5,
+  'm' => 6,
+  'n' => 6,
+  'o' => 6,
+  'p' => 7,
+  'q' => 7,
+  'r' => 7,
+  's' => 7,
+  't' => 8,
+  'u' => 8,
+  'v' => 8,
+  'w' => 9,
+  'x' => 9,
+  'y' => 9,
+  'z' => 9,
+}
+
+DIGIT_TO_LETTER = {
+  2 => 'abc',
+  3 => 'def',
+  4 => 'ghi', 
+  5 => 'jkl', 
+  6 => 'mno', 
+  7 => 'pqrs', 
+  8 => 'tuv', 
+  9 => 'wxyz',
+}
+
+class Node
+  attr_reader :value, :children
+
+  def initialize(value, children = [])
+    @value = value
+    @children = children
+  end
+
+  def inspect
+    "(#{value},#{children.map(&:inspect).join(",")})"
+  end
+end
+
+def trie_from(words)
+  trie = {}
+  words.each do |word|
+    current = trie
+    word.chars.each do |char|
+      current[LETTER_DIGIT_MAPPING[char]] ||= {}
+      current = current[LETTER_DIGIT_MAPPING[char]]
+    end
+    if !current.key?(-1)
+      current[-1] = [word]
+    else
+      current[-1] << word
+    end
+  end
+  return trie
+end
+
+def words_from(trie, digits)
+  return [] if digits.empty?
+  current = trie[digits.shift]
+  return [] if current.nil?
+
+  matches = []
+  until digits.empty?
+    digit = digits.shift
+    current = current[digit]
+    break if current.nil?
+
+    if current.key?(-1)
+      matches << current[-1]
+    end
+  end
+  return matches.flatten
+end
+
+def solution(input_digits, valid_words)
+  trie = trie_from(valid_words)
+  matches = []
+
+  tail = 0
+  until tail == input_digits.length do
+    window = input_digits[0..tail]
+    words = words_from(trie, window)
+    matches << words unless words.empty?
+    tail += 1
+  end
+  return matches.compact
+end
+
+assert_equal [["act"], ["bat"], ["cat"]], solution([2, 2, 8], ["act", "bat", "cat", "acd", "test"])