0208. Implement Trie (Prefix Tree)
==================================
题目信息
--------
:题号: 0208. 实现 Trie(前缀树)
:难度: Medium
:主题: Trie、前缀树、字符串、数据结构设计
:原题: `LeetCode 0208 `_
:重点: 用共享字符路径复用前缀,并用终止标记区分完整单词和普通前缀
题目重述
--------
设计一个 ``Trie`` 类,支持连续调用:构造函数建立空 Trie;``insert(word)`` 插入单词;
``search(word)`` 判断这个完整单词是否曾经插入;``startsWith(prefix)`` 判断是否存在某个
已插入单词以该前缀开头。
``word`` 和 ``prefix`` 只包含小写英文字母,长度位于 ``[1, 2000]``,三种操作总调用次数不超过
``3 * 10^4``。插入结果必须跨调用保留;一条字符路径存在,并不代表该路径的终点已经作为完整
单词插入。
自建示例
--------
完整单词和前缀必须分开判断:
.. code-block:: text
操作:insert("stone"),search("sto"),startsWith("sto"),insert("sto"),search("sto")
输出: false true true
解释:stone 建立了 sto 路径,但只有再次插入 sto 后,sto 的终点才标记为完整单词。
共享前缀和缺失分支:
.. code-block:: text
操作:insert("steam"),insert("step"),startsWith("ste"),search("stem")
输出: true false
解释:steam 与 step 共享 ste 节点,但 stem 在 m 处走不到已有分支。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Trie {
private:
struct Node {
std::array 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 把每个字符位置变成树上的一层。公共前缀只建立一份节点,单词的后缀从分叉处继续创建:
.. code-block:: text
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")``:
.. list-table::
:header-rows: 1
* - 操作
- 路径状态
- 终点标记
- 返回值
* - 插入 apple
- 建立 ``a-p-p-l-e``
- 只在 ``e`` 为真
- —
* - 查询 app
- 走到 ``p`` 成功
- ``p`` 为假
- ``false``
* - 前缀 app
- 走到 ``p`` 成功
- 不检查 ``p``
- ``true``
* - 插入 app
- 路径全部复用
- ``p`` 设为真
- —
* - 查询 app
- 走到 ``p`` 成功
- ``p`` 为真
- ``true``
缺失字符分支会让 ``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 的任意非空查询都会在第一处缺失链接返回假。