题目重点：哈希集合可查完整词，但Trie让共享前缀和后续接口可扩展。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- search为完整单词是否已add；不是prefix search，空词可加入。
- 按Unicode code point为边，不自动做大小写/Unicode归一化。
解题路线
- root是字符→子节点映射。add逐字符沿已有节点或新建，到词末记terminal。重复add幂等。
- search每字符必须存在对应边，走完仍需terminal；否则仅存在前缀不能说是完整词。用唯一object作terminal键，避免与任意字符冲突。
- 单纯完整词membership时hashset可能更简洁，但prefix枚举、最长前缀、通配匹配等要求使Trie有价值；复杂度比较含字符哈希/读取成本。
手动走一遍
add apple后search app=False；再add app为True，不破坏apple。空词terminal在root，search空串仅在add空串后True。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class Trie:
def __init__(self):
self.root={}
self.end=object()
def add(self,word):
node=self.root
for c in word:node=node.setdefault(c,{})
node[self.end]=True
def search(self,word):
node=self.root
for c in word:
if c not in node:return False
node=node[c]
return self.end in node
复杂度
一次add/search期望O(L)字符步，总存储O(所有不同前缀数)且哈希节点开销可能较大。全词hashset哈希也需读L字符，并非字符串长度无关O(1)。
易错点与追问
容易失分的边界
- 没有末尾标记会混淆app和apple。
- 每节点固定26数组只适合明确小写ASCII域，Unicode不可直接映射。
继续深挖
- delete一个词时如何保留其他词共享的前缀？
- 只匹配一个字符的通配符与任意长度*分别需要怎样的搜索状态？
