AC Python Solution


  • 46
    T
    class TrieNode:
    # Initialize your data structure here.
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.is_word = False
    
    class Trie:
    
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        current = self.root
        for letter in word:
            current = current.children[letter]
        current.is_word = True
    
    def search(self, word):
        current = self.root
        for letter in word:
            current = current.children.get(letter)
            if current is None:
                return False
        return current.is_word
    
    def startsWith(self, prefix):
        current = self.root
        for letter in prefix:
            current = current.children.get(letter)
            if current is None:
                return False
        return True

  • 0
    W

    @tusizi

    A brilliant clean Python solution. Thanks!


  • 0
    A

    Great Solution!


  • 0
    S

    How do you implement delete(self, word) in this code?


  • 0
    M

    @svkrish24 How about this?

    def delete(self, word):
        if not self.search(word):
            return False
        current = self.root
        for letter in word:
            if len(current.children) == 1:
                del current.children[letter]
                return True
            current = current.children.get(letter)
        return True
            
    
                        
        
    

  • 0
    S

    @martingale This doesn't work. If we have words "when" and "what" in the trie, you code will delete both the words when we try to delete either.


  • 0
    S
    This post is deleted!

  • 0
    L

    Thanks! very concise solution!


  • 0
    L

    I think the code can be cleaner if you get rid of the self.root = TrieNode()

    The TrieNode class is not necessary.
    You can simple define children and is_word in the Trie, and get rid of root.
    Use current = self instead of current = self.root.

    The idea behind this modification is that, a child of a Trie is a Trie


  • 1
    L

    This is my implementation:

    class Trie(object):
        def __init__(self):
            self.end = False
            self.c = {}
    
        def insert(self, word):
            node = self
            for w in word:
                if w not in node.c:
                    node.c[w] = Trie()
                node = node.c[w]
            node.end = True
                
        def prefixnode(self,word):
            node = self
            for w in word:
                if w not in node.c:
                    return None
                node = node.c[w]
            return node
        
        def search(self, word):
            node = self.prefixnode(word)
            if not node:
                return False
            else:
                return True if node.end else False
                
        def startsWith(self, prefix):
            node = self.prefixnode(prefix)       
            return bool(node)
            
    

  • 0

    This is confusing to me. For instance let's say we have the string 'google'

    current.children[letter]
    ok current is root node on first iteration, with a dictionary children, we store 'g' in it on the first iteration

    on the second iteration 'g'.children['o'] ....how did 'g' become a node? I thought it was a value in the dictionary for the root node?


Log in to reply
 

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