Problem of The Day: Implement Trie (Prefix Tree)

Problem Statement

see problem

Intuition

To implement the trie, we need a dictionary or hash map to represent for a container storing the children node. At the end of each word, we need to have a flag indicating the node is the last node in a word.

Approach

The approach involves designing a Trie class with insert, search, and startsWith methods. The TrieNode class represents each node in the trie, containing children nodes and a flag indicating whether it represents a complete word. The insert method inserts a word into the trie by creating nodes for each character. The search method checks if a complete word exists in the trie. The startsWith method checks if a given prefix exists in the trie.

Complexity

• Time complexity: The time complexity for insert, search, and startsWith methods is O(L), where L is the length of the word or prefix being processed. This is because each character in the word or prefix requires constant time for node traversal.

• Space complexity: The space complexity is O(N * L), where N is the total number of characters in all inserted words, and L is the average length of the words. The trie structure stores the characters of each word, and the number of nodes in the trie is proportional to the total number of characters.

Code

class TrieNode:
    def __init__(self):
        self.children = defaultdict()
        self.is_word = False

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.is_word = True

    def search(self, word: str) -> bool:
        curr = self.root
        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return curr.is_word
        

    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for c in prefix:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return True
        


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Solution without creating TrieNode

class Trie:

    def __init__(self):
        self.data = {}
        

    def insert(self, word: str) -> None:
        root = self.data
        for c in word:
            if c not in root:
                root[c] = {}
            root = root[c]

        root['final'] = True


    def search(self, word: str) -> bool:
        root = self.data

        for c in word:
            if c not in root:
                return False
            root = root[c]
        
        return 'final' in root.keys()
        

    def startsWith(self, prefix: str) -> bool:
        root = self.data

        for c in prefix:
            if c not in root:
                return False
            root = root[c]
        
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)