Tries: Contacts Discussions |

9 years ago+ 3 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:

class TrieNode(object):

    def __init__(self, char):
        self.char = char
        self.children = []
        self.is_word = False
        # the number of words this prefix is part of
        self.words_count = 0  
        
    def get_child(self, c):
        for child in self.children:
            if child.char == c:
                return child
        return None

class Trie(object):

    def __init__(self):
        self.root = TrieNode("*")  # token root char

    def add(self, word):
        curr = self.root
        for c in word:
            next_node = curr.get_child(c)
            if next_node is None:
                next_node = TrieNode(c)
                curr.children.append(next_node)
            next_node.words_count += 1
            curr = next_node
        curr.is_word = True

    def find(self, prefix):
        curr = self.root
        for c in prefix:
            next_node = curr.get_child(c)
            if next_node is None:
                return 0  # prefix not found
            curr = next_node

        return curr.words_count

Cookie support is required to access HackerRank