用 Trie 而不是 dict 做前缀匹配是因为 Trie 将查询复杂度从 O(N×M) 降至 O(M)，插入和 starts_with 均按字符逐层操作，search 要求路径存在且 is_end 为 True，而 starts_with 只需路径可达。
为什么用 Trie 而不是 dict 做前缀匹配？
因为 dict 的 keys() 遍历 + str.startswith() 是 O(N×M) 复杂度（N 是键数量，M 是前缀长度），而 Trie 可将前缀查询降到 O(M)，尤其在词典大、查询频繁时优势明显。但别指望它自动排序或支持通配符——它只负责“有没有以某串开头”。
如何设计节点结构和插入逻辑？
每个节点只需两个核心字段：children（字典映射字符到子节点）和 is_end（标记是否为单词结尾）。插入时逐字符下钻，不存在就新建节点；结尾处设 is_end = True。
常见错误是把字符串整体当 key 存进 children，其实应按单字符拆解：
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
<p>class Trie:
def <strong>init</strong>(self):
self.root = TrieNode()</p><pre class='brush:python;toolbar:false;'>def insert(self, word: str):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True怎么高效实现 starts_with 查询？
关键不是返回所有匹配词（那得 DFS 回溯），而是快速判断是否存在以某前缀开头的词。只需从根出发，按前缀字符逐层查找，中途任一字符缺失即返回 False；走完前缀后只要到达有效节点（不管 is_end 是否为 True），就说明有词以它开头。
立即学习“Python免费学习笔记（深入）”；
python-script-generator
下载
快速生成专业的 Python 脚本和应用代码。一键创建完整项目结构，支持CLI、API、爬虫、Bot、Django等多种项目类型，包含完整的项目结构、配置文件、依赖管理、测试、README和文档。
容易踩的坑：
- 误判空字符串：空前缀应始终返回
True（所有词都以空串开头） - 查到中途节点就停：比如插入
"apple"，查"app"时不能因node.is_end == False就返回False - 没处理非 ASCII 字符：
children用dict没问题，但若确定只有小写字母，可用长度 26 的 list 优化空间
简版实现：
def starts_with(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True # 只要能走到这里，就说明前缀存在
要不要加 search 方法？它和 starts_with 有什么区别？
search 要求整词存在，所以除了路径存在，还必须检查最终节点的 is_end == True；而 starts_with 只关心路径可达性。两者共享大部分逻辑，但语义不同，别混用。
性能影响点：
- 如果只用前缀匹配，
is_end字段可省略（节省内存） - 若需统计以某前缀开头的词数，可在节点加
count字段，插入时沿途递增 - Python 中频繁创建
TrieNode实例可能触发 GC，高频场景建议用__slots__ = ['children', 'is_end']减少内存开销
真正复杂的是并发读写——Trie 本身无内置线程安全，多线程插入需手动加锁，而只读查询可安全并发。
