My python solution


  • 26
    H
    class TrieNode:
            # Initialize your data structure here.
            def __init__(self):
                self.word=False
                self.children={}
        
        class Trie:
        
            def __init__(self):
                self.root = TrieNode()
        
            # @param {string} word
            # @return {void}
            # Inserts a word into the trie.
            def insert(self, word):
                node=self.root
                for i in word:
                    if i not in node.children:
                        node.children[i]=TrieNode()
                    node=node.children[i]
                node.word=True
        
            # @param {string} word
            # @return {boolean}
            # Returns if the word is in the trie.
            def search(self, word):
                node=self.root
                for i in word:
                    if i not in node.children:
                        return False
                    node=node.children[i]
                return node.word
        
            # @param {string} prefix
            # @return {boolean}
            # Returns if there is any word in the trie
            # that starts with the given prefix.
            def startsWith(self, prefix):
                node=self.root
                for i in prefix:
                    if i not in node.children:
                        return False
                    node=node.children[i]
                return True
                
        
        # Your Trie object will be instantiated and called as such:
        # trie = Trie()
        # trie.insert("somestring")
        # trie.search("key")

  • 1
    C

    code similar with you but add word frequency count.

    class TrieNode(object):
        # Initialize your data structure here.
        def __init__(self,k):
            self.v = 0
            self.k = k
            self.children = {}
            
    class Trie(object):
    
        def __init__(self):
            self.root = TrieNode(None)
    
        # @param {string} word
        # @return {void}
        # Inserts a word into the trie.
        def insert(self, word):
            node = self.root
            for w in word:
                if w not in node.children:
                    node.children[w] = TrieNode(w)
                node = node.children[w]
            node.v += 1
            
        def _startsWith(self,prefix):
            """
            @param {string} prefix
            @return {TrieNode} or None
            """
            node = self.root
            for w in prefix:
                if w in node.children:
                    node = node.children[w]
                else:
                    return None
            return node
            
        # @param {string} word
        # @return {boolean}
        # Returns if the word is in the trie.
        def search(self, word):
            node = self._startsWith(word)
            if node and node.v:
                return True
            else:
                return False
            
        # @param {string} prefix
        # @return {boolean}
        # Returns if there is any word in the trie
        # that starts with the given prefix.
        def startsWith(self, prefix):
            if self._startsWith(prefix):
                return True
            else:
                return False
            
    
    # Your Trie object will be instantiated and called as such:
    # trie = Trie()
    # trie.insert("somestring")
    # trie.search("key")

  • 0
    A

    similar with your code

    class TrieNode(object)

    def __init__(self):
        self.isWord = False
        self.children = {}
    

    class Trie(object):

    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.isWord = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.isWord
    
    def startsWith(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True
    

  • 0
    X

    Can't be more clear.


Log in to reply
 

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