题目重点：维护词典并按前缀返回候选，区分词结束标记、空前缀和输出排序成本。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 补充问点明确需要按prefix查询，基础题号与返回格式没有完整给定。练习定义add、contains和prefix_words，后者返回全部不同词且字典序；不担保实际题只要此API。
- 精确区分大小写和Unicode码点，词典允许空词，空前缀返回全部词。重复插入同词不创建重复候选；删除/TopK权重不是基础操作。
解题路线
- 每字符沿child map下降，词尾用None键标记，避免用#与合法字符冲突。contains必须既找到节点又有terminal，前缀存在不代表完整词。
- prefix_words先沿前缀找到子树，再迭代DFS收集terminal对应文字。不存在前缀返回[]；词本身也是前缀匹配，应在子树根检查terminal。
- 示例存stack的完整path字符串，便于读取，但每次text+ch有复制成本；结果统一sorted实现练习的字典序，不把dict遍历顺序当排序。
- 若只要是否存在前缀，无需展开子树；若需要最多K候选，可按字典序遍历/缓存，但频繁更新要维护缓存一致性。频率TopK还需权重与并列合同，不能靠当前字典序实现。
手动走一遍
词典[car,cat,ca]，contains(ca)true、contains(c)false；prefix_words(ca)=[ca,car,cat]。词典含#字符时仍合法，因为terminal不是字符串#。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class PrefixDictionary:
def __init__(self,words=()):
self.root={}
for word in words:self.add(word)
def add(self,word):
node=self.root
for ch in word:node=node.setdefault(ch,{})
node[None]=True
def _node(self,text):
node=self.root
for ch in text:
if ch not in node:return None
node=node[ch]
return node
def contains(self,word):
node=self._node(word)
return node is not None and None in node
def prefix_words(self,prefix):
node=self._node(prefix)
if node is None:return []
result=[];stack=[(node,prefix)]
while stack:
current,text=stack.pop()
if None in current:result.append(text)
for ch,child in current.items():
if ch is not None:stack.append((child,text+ch))
return sorted(result)
复杂度
构建读取总字符D，节点O(D)，contains长度L平均O(L)map访问。prefix枚举需访问子树V节点，当前路径复制成本按各访问节点路径长度之和计；R结果排序还需O(R log R)比较且比较成本随字符长度增加。stack及路径复制也需空间，不能说所有prefix请求O(L)。
易错点与追问
容易失分的边界
- 仅存在child路径就返回完整词true。
- 用合法字符作为terminal导致碰撞。
- 漏掉结果输出/排序/字符串复制成本。
继续深挖
- 若要删除词，如何删除terminal但保留其他词共享节点？
- 空前缀结果巨大时怎样分页且保持版本稳定？
