Python solution with "end-of-word" character


  • 0
    R

    Submitted twice, the time range 83%-45%

    class TrieNode(object):
        def __init__(self,v=None):
            """
            Initialize your data structure here.
            """
            self.v = v
            self.children_dict = dict()  # val to node
    
    class Trie(object):
    
        def __init__(self):
            self.root = TrieNode()
    
        def insert(self, word):
            """
            Inserts a word into the trie.
            :type word: str
            :rtype: void
            """
            n = self.root
            for w in word+'\\':  #assume no '\' in word
                if w not in n.children_dict:
                    n.children_dict[w] = TrieNode(w)
                n = n.children_dict[w]
    
    
        def search(self, word):
            """
            Returns if the word is in the trie.
            :type word: str
            :rtype: bool
            """
            return self.startsWith(word+'\\')
            
    
        def startsWith(self, prefix):
            """
            Returns if there is any word in the trie
            that starts with the given prefix.
            :type prefix: str
            :rtype: bool
            """
            n = self.root
            for w in prefix:
                if w not in n.children_dict:
                    return False
                n = n.children_dict[w]
            return True

Log in to reply
 

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