My AC Python solution


  • 3
    R
    class TrieNode:
        # Initialize your data structure here.
        li = []
        hasValue = False
        def __init__(self):
            self.li = [None]*26
            self.hasValue = False
    
    class Trie:
    
        def __init__(self):
            self.root = TrieNode()
    
        # @param {string} word
        # @return {void}
        # Inserts a word into the trie.
        def insert(self, word):
            def inserthelp(word,root,index):
                c = ord(word[index])-97
                if not root.li[c]:
                    root.li[c] = TrieNode()
                if index+1==len(word):
                    root.li[c].hasValue = True
                else:
                    inserthelp(word,root.li[c],index+1)
            if len(word):
                inserthelp(word,self.root,0)
    
        # @param {string} word
        # @return {boolean}
        # Returns if the word is in the trie.
        def search(self, word):
            def searchhelp(word,root,index):
                c = ord(word[index]) - 97
                if not root.li[c]:
                    return False
                if index+1==len(word):
                    return root.li[c].hasValue
                else:
                    return searchhelp(word,root.li[c],index+1)
            if len(word):
                return searchhelp(word,self.root,0)
            else:
                return True
    
        # @param {string} prefix
        # @return {boolean}
        # Returns if there is any word in the trie
        # that starts with the given prefix.
        def startsWith(self, prefix):
            def startshelp(word,root,index):
                c = ord(word[index])-97
                if not root.li[c]:
                    return False
                if index+1==len(word):
                    return True
                else:
                    return startshelp(word,root.li[c],index+1)
            if len(prefix):
                return startshelp(prefix,self.root,0)
            else:
                return True

  • 0
    S

    It looks that solution with dictionary works faster here. And it covers common case:

    class TrieNode:
    def __init__(self):
        self.flag = False
        self.children = {}
        
    class Trie:
    
        def __init__(self):
            self.root = TrieNode()
    
        def insert(self, word):
            cur = self.root
            for c in word:
                if not c in cur.children:
                    cur.children[c] = TrieNode()
                cur = cur.children[c]
            cur.flag = True
            
        def search(self, word):
            res, node = self.childSearch(word)
            if res:
                return node.flag
            return False
    
        def startsWith(self, prefix):
            return self.childSearch(prefix)[0]
            
        def childSearch(self, word):
            cur = self.root
            for c in word:
                if c in cur.children:
                    cur = cur.children[c]
                else:
                    return False, None
            return True, cur

  • 1
    C

    My solution is similar to sergey11's solution but uses a defaultdict:

    import collections
    
    class TrieNode:
        def __init__(self, exists=False):
            self.exists = exists
            self.children = collections.defaultdict(TrieNode)
    
    class Trie:
        def __init__(self):
            self.root = TrieNode()
    
        def insert(self, word):
            self.searchRoot(word, False).exists = True
    
        def search(self, word):
            childRoot = self.searchRoot(word)
            return childRoot and childRoot.exists
    
        def startsWith(self, prefix):
            return bool(self.searchRoot(prefix))
    
        def searchRoot(self, word, shouldExist=True):
            root = self.root
            for c in word:
                if shouldExist and c not in root.children:
                    return False
                root = root.children[c]
            return root

  • 0
    C

    Its time consume,Runtime: 732 ms


Log in to reply
 

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