Python trie with defaultdict trick


  • 4
    S
    from collections import defaultdict
    
    def _trie():
        return defaultdict(_trie)
    
    TERMINAL = None
    
    class WordDictionary(object):
        def __init__(self):
            self.trie = _trie()
    
        def addWord(self, word):
            trie = self.trie
            for letter in word:
                trie = trie[letter]
            trie[TERMINAL]
    
        def search(self, word, trie=None):
            if trie is None:
                trie = self.trie
            for i, letter in enumerate(word):
                if letter == '.':
                    return any(self.search(word[i+1:], t) for t in trie.itervalues())
                if letter in trie:
                    trie = trie[letter]
                else:
                    return False
            return TERMINAL in trie
    

    Very similar with the other trie-based solution but uses a less known defaultdict trick to make tries easier to build.


  • 0
    T

    How does this prevent the value associated with key TERMINAL from showing up in t? It looks like it'll call search with trie=trie[TERMINAL]. If that's true and the pattern is longer than the depth at which this happens, then enumerate would still try to continue matching from the root (trie is None falls back to self.trie) in the next level of recursion.


  • 0
    Z

    @TWiStErRob I realize that this is a very old post. But just in case anyone would see this. trie[TERMINAL] is not None. It is an empty _trie. So it will not fall back to self.trie.


Log in to reply
 

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