Python solution with detailed explanation


  • 0
    G

    Implement Trie (Prefix Tree) https://leetcode.com/problems/implement-trie-prefix-tree/

    • prefix_terminal_node - Returns the terminal prefix node. If prefix is "abc", this method will return either None or the pointer to node "c".
    • Now using the terminal node pointer, we can derive the answer for search and startsWith.
    from collections import defaultdict
    class TrieNode(object):
        def __init__(self):
            self.next, self.val = defaultdict(TrieNode), None
        
    class Trie(object):
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.root = TrieNode()
    
        def insert(self, word):
            """
            Inserts a word into the trie.
            :type word: str
            :rtype: void
            """
            if word:
                root = self.root
                for ch in word:
                    root = root.next[ch]
                root.val = word
        
        def search(self, word):
            """
            Returns if the word is in the trie.
            :type word: str
            :rtype: bool
            """
            if word:
                root = self.root
                for ch in word:
                    if ch in root.next:
                        root = root.next[ch]
                    else:
                        break
                else:
                    return root.val is not None
            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:
                root = self.root
                for ch in prefix:
                    if ch in root.next:
                        root = root.next[ch]
                    else:
                        return False
                return True
            return False
    

Log in to reply
 

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