Trie struct

trie.rb

# Data structure for a Trie
# should look something like this internally
# {:a => {
#   :is_word => true
#   :b => {
#     :is_word => false
#     :a = > {
#       :is_word => false
#       :c => {
#         :is_word => false
#         :u => {
#           :is_word => false
#           :s => {
#             :is_word => true
#           }
#         }
#       }
#     }
#     :h => {
#       :o => {
#         :r => null
#       }
#     }
#   }
# }

class String
  def to_int
    default_index = 'a'.ord || 97
    self.downcase.ord - default_index
  end
end


class Trie
  attr_accessor :is_word

  def initialize(words=nil)
    @is_word = false
    @children = Array.new(26)
    loadWords(words) unless words.nil?
  end

  def loadWords(words)
    words = words.split
    words.each do |word|
      addWord(word)
    end
  end

  def addWord(word)
    puts "******************"
    puts "input word: #{word}"
    word_arr = word.chars.to_a
    puts "word array: #{word_arr.inspect}"
    first = word_arr.first.to_int
    puts "first char: #{word_arr.first}"
    puts "num of char: #{first}"

    child = @children[first]
    puts "child: #{child.inspect}"
    if child.nil?
      child = Trie.new
      @children[first] = child
    end

    if word_arr.length == 1
      return false if child.is_word
      child.is_word = true
    else
      (1..word_arr.length-1).each do |i|
        child.addWord(word_arr[i])
      end
    end

    child
  end

  def contains(str)
    result = getNode(str)
    result && result.is_word
  end

  def isPrefix(str)
    result = getNode(str)
    result && result.numOfChildren > 0
  end

  def numOfChildren
    @children.length
  end

  def getNode(str)
    for i in (0..str.length)
      idx = str[i].to_int
      child = @children[idx]
      if child.nil?
        return nil
      end
    end
    child
  end

end