0208. Implement Trie (Prefix Tree)¶
题目信息¶
- 题号:
实现 Trie(前缀树)
- 难度:
Medium
- 主题:
Trie、前缀树、字符串、数据结构设计
- 原题:
- 重点:
用共享字符路径复用前缀,并用终止标记区分完整单词和普通前缀
题目重述¶
设计一个 Trie 类,支持连续调用:构造函数建立空 Trie;insert(word) 插入单词;
search(word) 判断这个完整单词是否曾经插入;startsWith(prefix) 判断是否存在某个
已插入单词以该前缀开头。
word 和 prefix 只包含小写英文字母,长度位于 [1, 2000],三种操作总调用次数不超过
3 * 10^4。插入结果必须跨调用保留;一条字符路径存在,并不代表该路径的终点已经作为完整
单词插入。
自建示例¶
完整单词和前缀必须分开判断:
操作:insert("stone"),search("sto"),startsWith("sto"),insert("sto"),search("sto")
输出: false true true
解释:stone 建立了 sto 路径,但只有再次插入 sto 后,sto 的终点才标记为完整单词。
共享前缀和缺失分支:
操作:insert("steam"),insert("step"),startsWith("ste"),search("stem")
输出: true false
解释:steam 与 step 共享 ste 节点,但 stem 在 m 处走不到已有分支。
C++ 实现¶
#include <array>
#include <string>
class Trie {
private:
struct Node {
std::array<Node*, 26> child{};
bool terminal = false;
};
Node* root_ = new Node();
static void release(Node* node) {
if (node == nullptr) return;
for (Node* child : node->child) release(child);
delete node;
}
Node* walk(const std::string& text) const {
Node* current = root_;
for (char character : text) {
int index = character - 'a';
if (current->child[index] == nullptr) return nullptr;
current = current->child[index];
}
return current;
}
public:
Trie() = default;
~Trie() {
release(root_);
}
void insert(const std::string& word) {
Node* current = root_;
for (char character : word) {
int index = character - 'a';
if (current->child[index] == nullptr) {
current->child[index] = new Node();
}
current = current->child[index];
}
current->terminal = true;
}
bool search(const std::string& word) const {
Node* node = walk(word);
return node != nullptr && node->terminal;
}
bool startsWith(const std::string& prefix) const {
return walk(prefix) != nullptr;
}
};
题解¶
逐个字符串扫描会重复前缀工作¶
如果把已插入单词保存成字符串列表,search 可以逐个比较完整字符串,startsWith 则要
逐个比较前缀。多次查询相同前缀时,列表方案反复读取相同的开头字符;插入新单词也无法把已有
前缀的判断结果结构化保存。
Trie 把每个字符位置变成树上的一层。公共前缀只建立一份节点,单词的后缀从分叉处继续创建:
root -> s -> t -> e -> a -> m
\-> p
路径表示“这个字符序列曾作为某个单词的前缀出现过”,但还没有表示“这个字符序列本身是完整
单词”。因此每个节点还需要一个 terminal 标记;它只在 insert 走完整个单词后置为真。
三种操作共享一条路径游标¶
令 current 从根开始,依次处理字符串字符:
insert:子节点存在就复用,不存在就创建;走完后把当前节点标记为完整单词终点;search:走完整条路径后,必须再检查terminal;startsWith:只要路径走完就成功,不关心终点是否为完整单词。
这三个操作的差异被压缩到“查询结束后是否检查终止标记”,而不是复制三套字符遍历。固定小写
字母表可以把字符映射为 0..25 的数组下标,避免每层再搜索子节点。
路径不变量¶
任意操作完成后,Trie 保持以下状态:
从根到节点的边标签组成该节点对应的唯一字符前缀;
非空子链接只表示相应扩展前缀曾出现在某个成功插入单词中;
terminal == true当且仅当该节点对应的完整字符串曾被插入;插入只新增空缺分支或设置终点标记,不删除既有路径,不把真标记改回假;
查询只读节点,不改变后续调用可见的 Trie 状态。
插入 apple 时,a、ap、app、appl 都只是路径节点,只有 apple 的终点
被标记。之后插入 app 只需把已有 app 节点的 terminal 设为真,不需要复制共享前缀。
状态走读¶
依次执行 insert("apple")、search("app")、startsWith("app")、
insert("app")、search("app"):
操作 |
路径状态 |
终点标记 |
返回值 |
|---|---|---|---|
插入 apple |
建立 |
只在 |
— |
查询 app |
走到 |
|
|
前缀 app |
走到 |
不检查 |
|
插入 app |
路径全部复用 |
|
— |
查询 app |
走到 |
|
|
缺失字符分支会让 walk 立即返回空指针;它只说明当前字符串不是已有前缀,不会删除其他
分支或改变根节点。
代码分析¶
每个 Node 固定保存 26 个子指针和一个 terminal。insert 只在遇到空指针时分配新
节点,因此共享前缀不会重复占用路径;重复插入同一个单词也只是重复设置同一个布尔值。
walk 把“按字符走树”的状态集中到一个私有函数。search 必须同时要求节点存在和
terminal 为真,startsWith 只要求节点存在,这两个返回条件正好对应题目语义。
公共 API 的根对象跨调用保存 root_;析构函数递归释放所有节点,释放过程访问每个实际节点
一次。题目保证字符是小写 ASCII,因此 character - 'a' 始终落在 0 到 25,不需要额外的
编码分支。
复杂度与边界¶
设当前操作字符串长度为 L,Trie 节点总数为 N。insert、search、startsWith
都只沿一条路径移动,时间复杂度为 O(L);固定 26 个子指针使每个节点空间为常数,整体
空间为 O(N),其中 N 不超过所有成功插入单词的字符总数加根节点。
查询缺失分支时可以提前结束;空前缀不在题目输入范围内,但若扩展支持,根节点始终存在,
startsWith("") 可自然返回真。空 Trie 的任意非空查询都会在第一处缺失链接返回假。