We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
My solution uses trie with Python 3. All test cases pass.
Two algorithmic ingredients are important to performance here:
Use compressed trie: Wiki: Radix Tree, instead of the uncompressed trie, which is branched by each of the letters in a word. Split the child node when the new word sharing common prefiex with its existing key.
Use the "visited" variable to record how many times a node has been visited during adding so that tree traversal can be avoided when dealing with "find" command.
importfileinputclassNode:def__init__(self,children=None,is_leaf=False,visited=0):ifchildrenisNone:self.children={}else:self.children=childrenself.is_leaf=is_leafself.visited=visiteddefadd(root,name):node=rootnode.visited+=1forkeyinnode.children:pre,_key,_name=extract_prefix(key,name)if_key=='':# there is a match of a part of the keychild=node.children[key]returnadd(child,_name)ifpre!='':child=node.children[key]# need to split_node=Node(children={_key:child},visited=child.visited)delnode.children[key]node.children[pre]=_nodereturnadd(_node,_name)node.children[name]=Node(is_leaf=True,visited=1)deffind(root,name):node=rootforkeyinnode.children:pre,_key,_name=extract_prefix(key,name)if_name=='':returnnode.children[key].visitedif_key=='':returnfind(node.children[key],_name)return0defextract_prefix(str1,str2):n=0forc1,c2inzip(str1,str2):ifc1!=c2:breakn+=1returnstr1[:n],str1[n:],str2[n:]############root=Node()inputs=fileinput.input()first_line=inputs.readline()num_operations=int(first_line)foriiinrange(num_operations):_action,_name=inputs.readline().strip().split()if_action=='add':add(root,_name)elif_action=='find':print(find(root,_name))
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Contacts
You are viewing a single comment's thread. Return to all comments →
My solution uses trie with Python 3. All test cases pass.
Two algorithmic ingredients are important to performance here:
Use compressed trie: Wiki: Radix Tree, instead of the uncompressed trie, which is branched by each of the letters in a word. Split the child node when the new word sharing common prefiex with its existing key.
Use the "visited" variable to record how many times a node has been visited during adding so that tree traversal can be avoided when dealing with "find" command.