实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 true trie.search("app"); // 返回 false trie.startsWith("app"); // 返回 true trie.insert("app"); trie.search("app"); // 返回 true说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。保证所有输入均为非空字符串。 class Trie(object): def __init__(self): self.root = {} self.end = '#' def insert(self, word): node = self.root for char in word: node = node.setdefault(char, {}) node[self.end] = self.end def search(self, word): node = self.root for char in word: if char not in node: return False node = node[char] return self.end in node def startsWith(self, prefix): node = self.root for char in prefix: if char not in node: return False node = node[char] return True