题干与适用场景
实现一个保存单词集合的 Trie，支持四个操作：
insert(word)插入单词；同一单词重复插入时保持幂等。search(word)判断完整单词是否存在。startsWith(prefix)判断该前缀路径是否存在；对于非空前缀，这等价于至少有一个已存单词以它开头。delete(word)删除完整单词，并返回该单词原本是否存在。
假设 insert、search 和 delete 接收非空、仅含小写英文字母的单词。startsWith 还允许空前缀，并按本题 API 约定返回 true，因为该 API 在尚未插入单词时也把根路径定义为空前缀。实现只考虑内存内、单线程场景，不负责枚举或排序补全结果、持久化以及 Unicode 归一化；调用方负责输入校验。
这是一道适用于软件工程岗位的代表性数据结构编码题。核心任务是建模共享前缀，并区分“路径存在”和“单词在这里结束”。加入删除后，候选人必须真正理解这一区别：删除 app 时要保留 apple，删除最后一条独占后缀时则可以回收对应节点。
面试官考察点
第一个信号是能否从操作需求推导数据结构。哈希集合适合精确成员判断，但前缀查询需要扫描单词或维护额外索引。Trie 让每个前缀对应一条从根出发的路径，因此查询成本取决于输入长度，而不取决于已存单词数量。
第二个信号是终止标记。插入 apple 后，app 的路径已经存在，但该节点被标记为完整单词前，search("app") 仍应返回 false；startsWith("app") 只检查路径即可。两个操作可以复用同一个遍历方法，但最终判定条件必须分开。
第三个信号是删除安全性。清除终止标记已经完成逻辑删除。物理剪枝属于可选的内存回收，只能从末尾向上删除“既非单词终点、又没有子节点”的节点。这个规则同时保护更长单词和与目标共享较短前缀的单词。
最后还要看复杂度是否和代码一致，以及测试是否覆盖状态变化。使用 Map 的节点不必为每个稀疏节点预留 26 个子指针，但 Map 操作依赖语言运行时的平均性能假设。删除还保存了长度为 L 的路径，声称辅助空间为常数会和实现矛盾。
回答前需要澄清的问题
- 字符集是什么？ 仅含小写
a-z时可以用长度为 26 的数组；Unicode、大小写混合或稀疏字符集更适合 Map，并且可能需要归一化约定。 - 重复插入是否计数？ 本题保存集合，第二次插入保持幂等；多重集合需要单词计数和前缀计数。
- 删除返回什么？ 删除不存在的单词返回
false，只有真正移除一个已存完整单词时才返回true。 - 删除是否必须回收节点？ 本题进行安全剪枝。删除很少且内存宽裕时，只清除终止标记更简单，同样满足正确性。
- 空字符串能否作为单词？ 不能。允许查询空前缀，但不允许插入或精确查询空单词。
- 前缀操作只判断存在，还是需要列出结果？ 本题只返回布尔值；枚举匹配项还需要遍历子树，复杂度与输出和子树规模有关。
- 是否需要并发安全？ 不需要；并发读写需要同步机制或不可变快照设计。
30 秒回答框架
“我会让每个前缀对应一条从根节点出发的路径。每个节点用 Map 保存下一字符到子节点的映射，并用 isWord 标记这里是否有完整单词。插入时创建缺失节点并标记终点；精确查询遍历后检查标记，前缀查询只要求路径存在。删除先记录整条路径，清除终点标记，再从后向前删除没有子节点且不代表其他单词终点的节点。Map 方案下各操作期望为 O(L)，总空间为 O(C)，删除额外使用 O(L) 路径空间。”
分步骤深入解答
使用列表或无序单词集合时，前缀查询会随单词数量增长。排序数组可以通过二分查找定位第一个可能匹配的单词，适合只读或静态词典，但在线插入、删除会产生移动或重建成本。Trie 用逐字符节点的内存开销，换取对四个在线操作的直接支持。
核心不变量是：
每个已存单词的字符都形成一条从根到某节点的路径；当且仅当该路径表示一个已存完整单词时，终点节点的 isWord 为真。
插入扩展一条路径并打开最终标记。精确查询同时要求路径和标记存在；前缀查询只要求路径存在。删除只关闭一个标记，随后仅回收不会再被任何单词使用的后缀。
class TrieNode {
readonly children = new Map<string, TrieNode>()
isWord = false
}
class Trie {
private readonly root = new TrieNode()
insert(word: string): void {
let node = this.root
for (const character of word) {
let child = node.children.get(character)
if (!child) {
child = new TrieNode()
node.children.set(character, child)
}
node = child
}
node.isWord = true
}
search(word: string): boolean {
return this.walk(word)?.isWord ?? false
}
startsWith(prefix: string): boolean {
return this.walk(prefix) !== undefined
}
delete(word: string): boolean {
let node = this.root
const path: Array<[TrieNode, string, TrieNode]> = []
for (const character of word) {
const child = node.children.get(character)
if (!child) return false
path.push([node, character, child])
node = child
}
if (!node.isWord) return false
node.isWord = false
for (let index = path.length - 1; index >= 0; index -= 1) {
const [parent, character, child] = path[index]
if (child.isWord || child.children.size > 0) break
parent.children.delete(character)
}
return true
}
private walk(text: string): TrieNode | undefined {
let node = this.root
for (const character of text) {
const child = node.children.get(character)
if (!child) return undefined
node = child
}
return node
}
}可以用两个反例检查删除逻辑。存有 app 和 apple 时，删除 app 只清除第二个 p 上的终止标记；该节点还有子节点 l，因此停止剪枝，apple 仍可查到。存有 app 和 apt 时，删除 app 只移除最后一个 p；向上到共享的 ap 节点时，因为还有子节点 t，剪枝停止。
正确性可以按操作归纳。空 Trie 满足不变量。插入只改变一条路径和最终标记；两种查询不修改状态。成功删除先精确清除目标标记。每个被剪掉的节点都不是单词终点且没有子节点，因此既不表示其他单词，也不通向其他单词；遇到第一个终止或分叉节点就停止，所有剩余共享路径都会保留。
设 L 为输入长度，C 为当前已分配的字符节点数。在 Map 平均查找性能成立时，插入、精确查找和前缀查找的期望时间都是 O(L)。删除向前遍历并最多回收同样的 L 条边，期望时间也为 O(L)。Trie 总空间为 O(C)，上界由不同已存前缀的字符总量决定；删除保存的路径额外占用 O(L)。
固定小写字母表时，可以使用 Array<TrieNode | undefined>(26)，通过下标直接访问，单字符操作更可预测，但每个节点都预留 26 个引用。Map 只保存真实存在的边，也能处理更大字符集，代价是哈希和对象开销。选择依据应是字符集与节点稠密度。
验证要覆盖状态转换。先检查 startsWith("") === true、search("") === false 和空 Trie 删除；插入 app、apple、apt，再次插入 app；区分 search("ap") 与 startsWith("ap")；删除 app 后确认 apple 保留；再次删除应失败；最后删掉其余单词并确认对应前缀消失。随机测试可以用一个简单的 Set<string> 作参考，并通过扫描集合计算前缀查询结果。
需求只有精确成员判断时，哈希集合更短也通常更合适。词典静态且已排序时，二分查找可避免逐字符节点的内存开销。大量单分支长链占用内存时，基数树可以压缩这些链，但节点分裂和合并逻辑会更复杂。
高质量示范回答
“我会先确认字符集、重复语义，以及删除是否需要回收内存。这里假设输入是非空小写单词，采用集合语义，空前缀匹配，并在删除时安全剪枝。
每个 Trie 节点保存下一字符的边和一个终止标记。从根到节点的路径就是前缀，终止标记说明该路径同时是一个已存完整单词。插入会创建缺失子节点，只在最后打开标记；精确查询需要检查最终标记，startsWith 只要遍历成功即可。
删除时，我在遍历单词的同时记录父节点、字符边和子节点。路径缺失或最终节点没有终止标记时，直接返回 false 且不修改状态。否则先清除标记，再倒序检查；只有子节点没有孩子且不代表另一个单词终点时才删除这条边，遇到仍被使用的节点就停止。这样删除 app 不会影响 apple。
使用 Map 时，所有操作的期望时间都是 O(L)。总存储为 O(C) 个字符节点，删除的路径栈为 O(L)。我会测试空和缺失情况、重复插入、一个单词是另一个单词前缀、两条单词分叉，以及删除最后一个单词后的完整剪枝。如果只需要精确查找，我会直接使用哈希集合。”
常见错误
- 把每条可达路径都当成单词 → 只插入
apple后，search("app")错误地返回真 → 精确查询必须检查isWord。 - 让
startsWith也检查isWord→ 没有单独插入的合法前缀会被拒绝 → 路径存在就返回成功。 - 删除时清空或移除整条路径 → 删除
app会破坏apple→ 先清除终止标记，只剪掉非终止叶节点。 - 越过分叉节点继续剪枝 →
apt等其他单词会消失 → 子节点仍有孩子时停止。 - 越过另一个终止节点继续剪枝 → 删除长单词时会移除它的短前缀单词 → 子节点是单词终点时停止。
- 只有删除路径存在就返回成功 → 只插入
apple时删除app会误报或改坏状态 → 要求最终节点必须是终止节点。 - 重复插入时意外累计状态 → 集合语义被暗中改成多重集合 → 使用一个布尔标记，或明确改用计数契约。
- 声称四个操作都是常数时间 → 工作量会随输入长度增长 → 说明期望
O(L)以及 Map 假设。 - 声称删除不占额外空间 → 实现保存了用于反向剪枝的路径 → 报告
O(L)辅助空间，递归实现也有同样的栈上界。 - 无条件给每个节点分配 26 个孩子 → 稀疏或 Unicode 数据会浪费空间或违反字符集约定 → 澄清字符集后再选择数组或 Map。
- 只有精确查找仍使用 Trie → 节点开销没有换来产品需要的前缀能力 → 只做精确成员判断时优先哈希集合。
追问及应对
追问 1：如果重复单词需要计数，并且每次只删除一个实例呢？
把 isWord 改为 wordCount；需要前缀计数时，再给节点增加 prefixCount。插入沿路径递增计数，删除先确认 wordCount > 0，再沿同一路径递减，只有相关计数归零时才能剪枝。布尔实现无法区分插入一次和五次。
追问 2：如何返回自动补全的 Top K 结果？
定位前缀节点仍需 O(L)，但枚举子树的成本与输出和子树规模有关。查询量低时，可以现场遍历并排序；查询量高时，可以在每个节点缓存有限个已排序候选项，并在写入时更新，用额外内存和写放大换取读取延迟。分数和并列规则必须明确。
追问 3：如何支持 Unicode 和大小写不敏感匹配？
先定义归一化，再选择节点表示。例如，在插入和查询两侧使用同一种 Unicode 归一化形式与符合语言环境的大小写规则，并约定按码点还是字素簇迭代，子边使用 Map。只归一化查询或只归一化插入会产生永远匹配不到的路径。
追问 4：如何保证并发安全？
最简单的正确方案是在整个 Trie 外使用读写锁：插入和删除持写锁，精确与前缀查询持读锁。更细的节点锁需要固定加锁顺序并保护剪枝过程。更新很少时，不可变快照或根节点写时复制能让读取更简单。
追问 5：内存成为主要限制时怎么办？
先测量节点稠密度。固定数组在稀疏数据里可能占据主要空间，Map 也有对象和哈希开销。基数树可以压缩单分支链，三向搜索树可以减少子节点存储，静态词典还可以进一步压缩成最小有限状态结构；这些选择会改变更新复杂度和实现风险。
追问 6：通配符或最长前缀匹配会怎样改变遍历？
最长前缀匹配沿查询字符串前进，并记住经过的最深终止节点，仍然与查询长度线性相关。. 一类通配符会在对应位置遍历所有子节点，最坏工作量会随探索到的子树扩张。API 还需明确通配符语法，以及返回存在性、一个结果还是全部结果。