| 题目链接 | 208. 实现 Trie (前缀树) |
|---|---|
| 思路 | 模板题 - Trie树 |
| 题解链接 | 官方题解 |
| 关键点 | 无 |
| 时间复杂度 | \(O(\sum_{i}\#\text{word}_{i})\) |
| 空间复杂度 | \(O(\sum_{i}\#\text{word}_{i})\) |
代码实现：
class Trie:
def __init__(self):
self.children = [None] * 26
self.isEnd = False
def insert(self, word: str) -> None:
node = self
for ch in word:
ch = ord(ch) - ord('a')
if not node.children[ch]:
node.children[ch] = Trie()
node = node.children[ch]
node.isEnd = True
def search(self, word: str) -> bool:
node = self._searchPrefix(word)
return node is not None and node.isEnd
def startsWith(self, prefix: str) -> bool:
return self._searchPrefix(prefix) is not None
def _searchPrefix(self, prefix) -> "Trie":
node = self
for ch in prefix:
ch = ord(ch) - ord('a')
if not node.children[ch]:
return None
node = node.children[ch]
return node