0208. Implement Trie (Prefix Tree)

题目信息

题号:
  1. 实现 Trie(前缀树)

难度:

Medium

主题:

Trie、前缀树、字符串、数据结构设计

原题:

LeetCode 0208

重点:

用共享字符路径复用前缀,并用终止标记区分完整单词和普通前缀

题目重述

设计一个 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

建立 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 的任意非空查询都会在第一处缺失链接返回假。