Break a string Into valid words

BreakStringIntoWords

class BreakStr

  attr_reader :tree

  def initialize
    @tree = {}
    @dict = ["I", "am", "a", "happy", "hap", "sad", "silly", "with"]
  end

  def get_valid_prefixes(word)
    start,ending=0,0
    valid_prefix = []
    while (ending!=word.size+1) do
      prefix = word[start,ending]
      valid_prefix << prefix if @dict.include?(prefix)
      ending +=1
    end
    valid_prefix
  end


  def add(word,subtree=@tree)
    head_nodes = get_valid_prefixes(word)
    return subtree[:invalid] = true  if head_nodes.empty?
    head_nodes.each do |x|
      rest = word.split(x)[1]
      words_so_far = subtree[:words_so_far] ? subtree[:words_so_far] : []
      subtree[x] ||= {words_so_far: [x]+ words_so_far }
      if rest.nil?
        subtree[x][:valid] = true
      else
        add(rest, subtree[x])
      end
    end
  end


  def traversal(subtree=@tree)
    subtree.each_pair do |k,v|
      if k == :valid then
        p "Found a valid match"
        p "#{subtree[:words_so_far]}"
      end
      traversal(v) unless k.is_a? Symbol
    end
  end

end


b = BreakStr.new
b.add("Iamhappy")
p b.tree
b.traversal

b = BreakStr.new
b.add("Iamsillywithhappy")
p b.tree
b.traversal

Question: Break a String into valid words

Summary: Given a string "Iamhappy", identify valid words and find the maximum contiguous strings that are valid and that use up all the letters in the string.

I created a data structure based on a prefix/trie tree and simply stored it in the ruby hash. I wrote a function to identify the valid prefixes and made them keys. I recursively identified all the prefixes until the string was depleted, in which case I marked the leaf node as valid. Dead end leaf nodes were marked as invalid. To simplify the returning of all words, I cached the words at each recursive step and merged them with previous words at each level. I wrote a simple traverse function to print the solution.
{"I"=>{:words_so_far=>["I"], "a"=>{:words_so_far=>["a", "I"], :invalid=>true}, "am"=>{:words_so_far=>["am", "I"], "hap"=>{:words_so_far=>["hap", "am", "I"], :invalid=>true}, "happy"=>{:words_so_far=>["happy", "am", "I"], :valid=>true}}}}