Skip to content

Instantly share code, notes, and snippets.

@joseluistorres
Created March 27, 2017 16:40
Show Gist options
  • Save joseluistorres/db1d7c5a4ad1a383dd8101d62e51d06a to your computer and use it in GitHub Desktop.
Save joseluistorres/db1d7c5a4ad1a383dd8101d62e51d06a to your computer and use it in GitHub Desktop.
class Node
attr_accessor :children, :size
def initialize
@children = {}
@size = 0
end
def find_count(word, index)
return @size if index == word.length
child = get_node(word[index])
if !child
return 0
end
return child.find_count(word, index + 1)
end
def add(word)
add_word(word, 0)
end
def add_word(word, index)
@size += 1
return if index == word.length
current = word[index]
charCode = get_char_index(current)
child = get_node(current)
if !child
child = Node.new
set_node(current, child)
end
child.add_word(word, index + 1)
end
private
def get_char_index(character)
character.bytes[0] - 97
end
def get_node(character)
@children[get_char_index(character)]
end
def set_node(character, node)
@children[get_char_index(character)] = node
end
end
n = gets.strip.to_i
node = Node.new
for a0 in (0..n-1)
op,contact = gets.strip.split(' ')
if op == 'add'
node.add(contact)
else
puts node.find_count(contact, 0)
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment