z1002 hash

#   Memory limit exceeded, test 5, time 1.575, memory   82 888 КБ
codes = {
    'a' => '2', 'b' => '2', 'c' => '2', 'd' => '3', 'e' => '3', 'f' => '3', 'g' => '4', 'h' => '4', 'i' => '1',
    'j' => '1', 'k' => '5', 'l' => '5', 'm' => '6', 'n' => '6', 'o' => '0', 'p' => '7', 'q' => '0', 'r' => '7',
    's' => '7', 't' => '8', 'u' => '8', 'v' => '8', 'w' => '9', 'x' => '9', 'y' => '9', 'z' => '0',
}

while true
  phone = gets.chomp
  break if phone == '-1'
  words = {}
  gets.to_i.times {
    word = gets.chomp
    code = '';
    word.each_char { |letter| code += codes[letter]}
    words[code] = word
  }

  max_word_length = words.keys.max_by {|k| k.length}.length
  finds = [['']]
  phone.each_char.with_index { |number, index|
    to_delete = []
    to_add = []
    finds.each { |find|
      find[-1] += number
      if find.last.length > max_word_length
        to_delete.push(find)
        next
      end
      if index < phone.length - 1
        if words.key?(find.last)
          branch = []
          find.each {|part| branch.push(part.clone)}
          to_add.push(branch)
          find.push('')
        end
      elsif !words.key?(find.last)
        to_delete.push(find)
      end
    }
    to_delete.each { |find| finds.delete(find) }
    to_add.each { |find| finds.push(find) }
  }

  if (finds.empty?)
    puts 'No solution.'
  else
    shortest = finds.min_by { |find| find.length }
    answer = []
    shortest.each { |code| answer.push(words[code])}
    puts answer * ' '
  end
end