trie_using_hash.rb

# Implement a Trie using hash (You need to first figure out what operations the trie has to support)
# add, contains, word_count, remove, etc.
class Trie
  attr_accessor :root
  
  def initialize()
  	@root = {}
  end
  
  # returns false if already present
  def add(str)
  	cur = @root
  	new_word = false
  	str.chars.each do |c|
  		if !cur[c]
  			cur[c] = {} 
  			new_word = true
  		end
  		cur = cur[c]
  	end

	if !cur["end"]
		cur["end"] = {}
		new_word = true
	end
  	new_word
  end
  
  def contains(word)
  	cur = @root
  	word.chars.each do |c|
  		return false if !cur[c]
  		cur = cur[c]
  	end
  	cur["end"]
  end
end
t = Trie.new
t.add("abc")
t.add("ab")
t.add("abc")