z1002 two arrays

# Time limit exceeded, test 4, time 2.043, memory   780 КБ
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 = []
  wcodes = []
  gets.to_i.times {
    word = gets.chomp
    code = '';
    word.each_char { |letter| code += codes[letter]}
    next if words.include? word
    words.push(word)
    wcodes.push(code)
  }

  xcodes = wcodes.sort()

  max_word_length = words.max_by {|k| k.length}.length
  min_world_length = words.min_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
      isset = find.last.length >= min_world_length && xcodes.include?(find.last)
      if index < phone.length - 1
        if isset
            branch = []
            find.each {|part| branch.push(part.clone)}
            to_add.push(branch)
            find.push('')
        end
      elsif !isset
        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[wcodes.index(code)])}
    puts answer * ' '
  end
end