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.
I don't think you need that much complexity. As the problem states, only lowercase English characters are used, so it's a constant number and you could just use a list and append as you find the chars, only using the memory allocations required at a time, iterating through children should not be an issue.
In the case of the original post by jcchuks1, I think the problem may be due to other issue.
Surprisingly the following solution worked for me using a dynamic array, after failing with dicts and sets (with the proper hashing). Probably a linked list would work too:
classTrieNode(object):def__init__(self,char):self.char=charself.children=[]self.is_word=False# the number of words this prefix is part ofself.words_count=0defget_child(self,c):forchildinself.children:ifchild.char==c:returnchildreturnNoneclassTrie(object):def__init__(self):self.root=TrieNode("*")# token root chardefadd(self,word):curr=self.rootforcinword:next_node=curr.get_child(c)ifnext_nodeisNone:next_node=TrieNode(c)curr.children.append(next_node)next_node.words_count+=1curr=next_nodecurr.is_word=Truedeffind(self,prefix):curr=self.rootforcinprefix:next_node=curr.get_child(c)ifnext_nodeisNone:return0# prefix not foundcurr=next_nodereturncurr.words_count
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tries: Contacts
You are viewing a single comment's thread. Return to all comments →
I don't think you need that much complexity. As the problem states, only lowercase English characters are used, so it's a constant number and you could just use a list and append as you find the chars, only using the memory allocations required at a time, iterating through children should not be an issue. In the case of the original post by jcchuks1, I think the problem may be due to other issue.
Surprisingly the following solution worked for me using a dynamic array, after failing with dicts and sets (with the proper hashing). Probably a linked list would work too: