Given an input list of words and a string, output every different set of words that can make up that string

Problem:

Given an input list of words and a string, output every different set of words that you can find in the string from the given words. For example, input: word_list = ['dog', 'cats', 'sand', 'cat', 'and'], string = "catsanddog" output: [ ['cat', 'sand', 'dog'], ['cats', 'and', 'dog'] ]

My pseudo code is:

1. Create an array current_matches.

2. Loop through each character in the string, keeping track of the sub-word up to that character, and the current character.

3. Add the current character to all the matches in current_matches so that they can keep track of successive matches.

4. See if the sub-word is in the array. If it is, add that word to the current_matches array.

5. After the loop is done, check if any of the matches add up to the original string.

Perhaps I'm missing a key concept that would make this easier? I read about Tries 2 weeks ago, and it sounds like that could be it, but I'm not familiar enough with them.

def string_legos(list_of_words, string)
  # Make hash out of the words so that lookup is faster
  # when we scan the list of words to see if one exists
  dictionary = {}
  list_of_words.each do |word|
    dictionary[word] = true
  end
  current_matches = []
  string.length.times do |i|
    character = string[i]
    word = string[0..i]
    current_matches.each do |match|
      match.track(character)
    end
    if dictionary[word]
      current_matches << Match.new(word, dictionary)
    end
  end

  current_matches.select do |match|
    match.equals?(string)
  end
  current_matches
end

class Match
  def initialize(word, dictionary)
    @dictionary = dictionary.clone
    @words = []
    @current_string = ''
    @words << word
  end

  def track(character)
    @current_string << character
    if word_unused?
      mark_word_as_used
      @words << @current_string
      @current_string = ''
    end
  end

  def word_unused?
    @dictionary[@current_string]
  end

  def mark_word_as_used
    @dictionary[@current_string] = false
  end

  def equals?(string)
    @words.join == string
  end
end

Are there any glaring issues / optimizations you can see with this?