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.
How does this prevent the value associated with key
TERMINAL from showing up in
t? It looks like it'll call
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.