题目重点：从字典插入、完整词查询和前缀判断讲 Trie 节点不变量；公开帖没有通配符或分词要求，示例按明示契约实现。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版操作为 insert(word)、contains(word)、has_prefix(prefix)，按 Unicode code point 区分大小写；允许空串作为字典词。
- 不包括自动补全、词频、模糊编辑距离或删除，题目未明确这些操作。
解题路线
- 每个节点用字符→子节点映射；插入沿字符路径建缺失节点，末节点设置终止标志。相同前缀共享节点，不因另一个词更长而覆盖短词终止位。
- contains 走完整词路径后还必须检查终止标志；has_prefix 只要求路径存在。前者检验字典成员，后者检验至少某个已插入词以该字符串开头。
- 空字符串的终止标志在根节点；若字典从未插入任何词，空前缀是否为真需签契约，本训练版按节点路径存在返回真。
- 巨大字典按字符分支和内存成本考虑压缩 Trie 或磁盘索引；只做精确词查询且无前缀需求时，哈希集合通常更简单。
手动走一遍
插入 `car` 与 `cart`，contains(car/cart) 均真，contains(ca) 假但 has_prefix(ca) 真。插入空串后 contains(空串) 真；字符 `\0` 是普通字符，终止标志使用独立哨兵。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class Trie:
"""Training contract: exact word lookup and prefix existence, Unicode code points."""
END = object()
def __init__(self) -> None:
self.root: dict[str, dict] = {}
def insert(self, word: str) -> None:
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.END] = {}
def contains(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.END in node
def has_prefix(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True
复杂度
单次插入或查询长度为 L 的词需 O(L) 时间；最多 O(总输入字符数) 节点，实际映射指针开销较高。与哈希集合相比，前缀共享能减少重复字符存储但不保证所有语言/语料都省内存。
易错点与追问
容易失分的边界
- 把前缀存在当成完整词存在。
- 插入 `cart` 时清掉 `car` 的终止状态。
- 未经题目证据实现通配符或自动补全并称为面试原题。
- 忘记空串和特殊字符边界。
- 说 Trie 查询与词长无关。
继续深挖
- 字典需要删除词时怎样避免误删共享前缀？
- 如何返回前缀下排名最高的 K 个词？
- 为什么只查完整词时 HashSet 可能更合适？
- 百万词规模下如何估内存和持久化？
