字典树Trie模板

class Trie:
    def __init__(self):
        self.children = defaultdict(Trie)
        self.word = ""
        self.is_word = False
    def insert(self, word):
        cur = self
        for w in word:
            cur = cur.children[w]
        cur.is_word = True
        cur.word = word
    def search(self, word):
        cur = self
        for w in word:
            if w not in cur.children:
                return False
            cur = cur.children[w]
        return cur.is_word