208. 实现 Trie (前缀树)（中等）

Blind 75 › 208. 实现 Trie (前缀树)（中等）（第 1 章）

题目

实现一个「前缀树 Trie」，用来维护一组字符串，并支持三种操作：

insert(word)：把 word 存进去。
search(word)：word 是不是完整地被人存过；走得到结尾还不够，必须当初就是按“完整一个词”存的。
startsWith(prefix)：已存的词里，是否有某个词以 prefix 开头。

关键差别：search("ca") 要求真的存过 "ca"；而 startsWith("ca") 只要存过 "car"、"cat" 这类以 "ca" 开头的词就成立。

自造示例：依次插入 car、cat、dog，再做五次查询：

调用	返回	原因
`search("cat")`	`true`	`cat` 被完整插入过
`search("ca")`	`false`	树里有 `ca` 这条路径，但它只是前缀，没作为完整词插入
`startsWith("ca")`	`true`	`car / cat` 都以 `ca` 开头
`insert("ca")`	`null`	补插完整词 `ca`
`search("ca")`	`true`	这次真的存过了

约束：单词与待查前缀长度 1 ~ 2000；只含小写字母；三种操作的总调用次数不超过 3 × 10⁴。

思路

一句话：把字符串按字符逐位“走”进一棵树，公共前缀共享同一条路径，走到哪，哪就代表一个前缀。

先想最直白的：用一个数组把所有词存起来。插入 O(1)；但每次 search 都要跟每个存过的词逐一比较，startsWith 也要检查每个词的头部，最坏 O(词数 × 词长)。总调用可到 3 × 10⁴，词长可到 2000，会太慢。

再聪明一点：准备两个哈希集合——words 存完整词，prefixes 存所有前缀。插入时把一个词的每个前缀都丢进 prefixes。这样 search 和 startsWith 都变成随时间 O(词长) 的哈希查询。代价是：插一个长为 l 的词要造 l 个前缀串，时间 O(l²)、空间也 O(l²)，而且丢掉了“词与词共享前缀”的结构，后面想做自动补全、前缀计数都不顺手。

关键观察：很多字符串会共享前缀，比如 car 和 cat 都共享 ca。与其把每个词（甚至每个前缀）平铺复制，不如用一棵树共享：

根节点 = 空串。
每条边 = 追加一个字符。
从根走到某个节点的路径 = 一个前缀。
节点上加一个 end 标记，表示“到这里正好是一个完整插入过的词”。

于是 search 就是“沿边走到底，再看 end”；startsWith 就是“沿边走到底，只要走得到就算”。选定这个结构：每个字符串操作 O(l)，空间只与所有不同前缀的总长度相当。

解法

节点只存两样东西：26 个子节点指针（用 c - 'a' 当下标）+ 一个 end 布尔。

insert：从根出发，逐字符往下走；边不存在就新建节点；走到最后一个字符后，把该节点 end 置 true。
search：从根逐字符走；半路发现边为空就返回 false；走到尾返回 node.end。
startsWith：和 search 一样地走，但走到尾直接返回 true，不查 end。

以上面的 car、cat、dog、ca 为例，最终树形是：

root
├── c
│   └── a ★
│       ├── r ★
│       └── t ★
└── d
    └── o
        └── g ★   （★ 表示 end=true，是完整词）

建树过程一目了然：

操作	走的路径	新建	标记
`insert("car")`	c → a → r	c、a、r 三个节点	r 的 `end=true`
`insert("cat")`	c → a 复用，再走 t	只新建 t	t 的 `end=true`
`insert("dog")`	d → o → g	整条新建	g 的 `end=true`
`insert("ca")`	c → a 全复用	无	a 的 `end=true`

查询时，“走得到”与“是不是完整词”分开判断：

查询	走过的节点	走到终点	返回
`search("cat")`	c → a → t	t 的 `end=true`	`true`
`search("ca")`	c → a	a 的 `end=false`（此时还没插 ca）	`false`
`startsWith("ca")`	c → a	走得到，不需要看 `end`	`true`

下图把上面 3 个步骤串成流程，并逐步演示：

208. 实现 Trie (前缀树)（中等）解法步骤流程图 — 图① 解法步骤流程图（共 3 步）。

208. 实现 Trie (前缀树)（中等）按步骤逐步执行的动画 — 动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →

class TrieNode {
public:
 TrieNode* child[26];
 bool end;  TrieNode() : end(false) {
 for (int i = 0; i < 26; ++i) {
 child[i] = nullptr;
 }
 }
};  class Trie {
public:
 Trie() {
 root = new TrieNode();
 }  void insert(string word) {
 TrieNode* node = root;
 for (char c : word) {
 int i = c - 'a';
 if (node->child[i] == nullptr) {
 node->child[i] = new TrieNode();
 }
 node = node->child[i];
 }
 node->end = true;
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。

一木科技

一木科技