BinarySearch 0735 Trie

Problem statement

https://binarysearch.com/problems/Trie/

Solution

Equal to Leetcode 0208 Implement Trie (Prefix Tree), just rename functions.

Complexity

Time complexity of all operations is O(n), where n is the size of word. Space complexity is O(M), where M is total lengths of all words.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_node = 0

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

    def add(self, word):
        root = self.root
        for symbol in word:
            root = root.children.setdefault(symbol, TrieNode())
        root.end_node = 1
        
    def searchHelper(self, word):
        root = self.root
        for symbol in word:
            if symbol in root.children:
                root = root.children[symbol]
            else:
                return -1

        return 1 if root.end_node == 1 else 0  

    def exists(self, word):
        return self.searchHelper(word) == 1

    def startswith(self, p):
        return self.searchHelper(p) >= 0