力扣 208. 前缀树

字典树

class Tree:
    def __init__(self, val):
        self.val = val
        self.next = {}

class Trie:

    def __init__(self):
        self.tree = Tree(0)

    def insert(self, word: str) -> None:
        tree = self.tree
        for w in word:
            if w not in tree.next.keys():
                tree.next[w] = Tree(w)

            tree = tree.next[w]
        tree.next[-1] = True

    def search(self, word: str) -> bool:
        tree = self.tree
        for w in word:
            if w not in tree.next:
                return False
            tree = tree.next[w]
        
        return tree.next.get(-1, False)

    def startsWith(self, prefix: str) -> bool:
        tree = self.tree
        for w in prefix:
            if w not in tree.next:
                return False
            tree = tree.next[w]
        return True