Python solution


  • 0
    V
    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        self._insert(word, 0 , self.root)
    
    def _insert(self, word, index, node):
        head = word[index]
        child_node = None
        if head not in node.path:
            child_node = TrieNode()
            child_node.val = head
            node.path[head] = child_node
        else:
            child_node = node.path[head]
        if len(word) == index+1:
            child_node.path[' '] = '__END__'
            return
        elif len(word)>index+1:
            self._insert(word, index+1, child_node)
        
        
    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        if word is None:
            return False 
        return self._search(word, 0, self.root)
        
    def _search(self, word, index, node):
        head = word[index]
        if head not in node.path:
            return False 
        child_node = node.path[head]
        if len(word) ==index+1  and ' ' in child_node.path:
            return True
        elif len(word)>index+1:
            return self._search(word, index+1, child_node)
        else:
            return False
        
        
    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie
        that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        if prefix is None or len(prefix) == 0:
            return False 
        return self._startswith(prefix, 0, self.root)
        
    def _startswith(self, word, index, node):
        head = word[index]
        if head not in node.path:
            return False 
        child_node = node.path[head]
        if len(word) ==index+1:
            return True
        elif len(word)>index+1:
            return self._startswith(word, index+1, child_node)
        else:
            return False

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.