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:Create an array current_matches.Loop through each character in the string, keeping track of the sub-word up to that character, and the current character.Add the current character to all the matches in current_matches so that they can keep track of successive matches.See if the sub-word is in the array. If it is, add that word to the current_matches array.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_matchesendclass 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  endendAre there any glaring issues / optimizations you can see with this?
Given an input list of words and a string, output every different set of words that can make up that string
ruby;trie