ruby iterate through hash

Question

I have a hash of hashes. This hash has a dictionary. I need to find all matches in it which have the same root. For example, I have:

#<Trie:0x00000001bf9a40 @root={
  "m"=>{"a"=>{"x"=>{
    :end=>true,
    "i"=>{"m"=>{
      :end=>true,
      "i"=>{"m"=>{"l"=>{"i"=>{"a"=>{"n"=>{:end=>true}}}}}}
    }},
    "w"=>{"e"=>{"l"=>{"l"=>{:end=>true}}}}
  }}}
}>

and words "max", "maxim", "maximilian", "maxwell". How do I get all words in this hash by the root? For example

t = Trie.new
t.add( .....# now we added words
t.find('max')
#result all words which begins from 'max'
t.find('maxim')
#result all words which begins from 'maxim' => maxim, maximilian

Answer 1

It looks like my find method is very similar to @sawa's. (I believe @sawa is the person who first taught me to use inject with &:[] in cases this like this, so that's fitting.)

Given:

class Trie
  def initialize(root)
    @root = root # Just a shortcut to use your data and focus on your question
  end

  # Recurses through Hash `h` to find all words starting with `s`
  def words(h, s, a=[])
    h.each do |k, v|
      if k == :end
        a << s
      else
        words(v, s+k, a)
      end
    end

    a
  end

  private :words

  def find(start)
    words(start.chars.inject(@root, &:[]), start) rescue []
  end
end

t = Trie.new({"m"=>{"a"=>{"x"=>{:end=>true,
                              "i"=>{"m"=>{:end=>true,
                                         "i"=>{"m"=>{"l"=>{"i"=>{"a"=>{"n"=>{:end=>true}}}}}}}},
                              "w"=>{"e"=>{"l"=>{"l"=>{:end=>true}}}}}}}})

You can do:

t.find('max')
# => ["max", "maxim", "maximimlian", "maxwell"]
t.find('maxi')
# => ["maxim", "maximimlian"]
t.find('maximi')
# => ["maximimlian"]
t.find('maxw')
# => ["maxwell"]
t.find('x')                                                                                                                                                                                                        
# => []