LC208数据结构Trie · 前缀树字符前缀路网

实现 Trie (前缀树)

实现 insert/search/startsWith 词典。

题目是什么

实现 insert/search/startsWith 词典。

解决什么问题

当前字符边是否存在，走到这里是否已经构成完整单词？

核心结论

26 叉 Trie 结点带 isEnd;逐字符向下走或建。

01交互算法精讲

先说结论：这道题到底解决什么

怎样从“实现 insert/search/startsWith 词典。”推导出 Trie · 前缀树，并证明每次状态变化都不会漏掉答案？

中心结论：26 叉 Trie 结点带 isEnd;逐字符向下走或建。

读完必须能回答

1.暴力方案在哪里重复计算，为什么仍然是正确基线？
2.当前字符边是否存在，走到这里是否已经构成完整单词？
3.不变量“从根到 isEnd 路径拼出单词。”为什么能保证算法安全前进？

02交互算法精讲

完整题目与题意拆解

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

在本站主例中，实现 insert/search/startsWith 词典。

算法最终需要得到或观察：search("apple") true。

把题目翻译成状态

• 输入：实现 insert/search/startsWith 词典。
• 机器需要维护：当前结点、字符索引。
• 最终可观察结果：search("apple") true。

动画 1 · 题意扫描

先看清算法到底要维护什么

先建立输入、目标、输出和第一批状态，不急着进入模板。

Step 1/20%

题目与输入建立输入、目标与算法心智

Trie:边标字符,结点标记单词结尾

正在加载算法场景...

发生了什么

实现 insert/search/startsWith 词典。

为什么

26 叉 Trie 结点带 isEnd;逐字符向下走或建。

下一步

根结点 children 为空：root = new TrieNode()

当前状态

当前结点、字符索引。

当前 Go 代码 · 高亮第 7 行

4}5 6/** Initialize your data structure here. */7func Constructor() Trie {8	return Trie{isWord: false, children: make(map[rune]*Trie)}9}10

03交互算法精讲

第一层方案：暴力做法

逐个单词完整比较会重复扫描共同前缀；Trie 让共享前缀只建立和经过一次。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选，但没有保存已经确认的信息，因此同一状态会被重新计算。

动画 2 · 暴力重复

重复工作究竟发生在哪里

把重复读取或重复搜索的区域明确标出，再决定优化必须保存什么。

Step 1/20%

先做对：建立暴力基线枚举所有候选并完整验证

Trie:边标字符,结点标记单词结尾

正在加载算法场景...

发生了什么

逐个单词完整比较会重复扫描共同前缀；Trie 让共享前缀只建立和经过一次。

为什么

暴力法覆盖所有候选，因此可以作为题意校验版本；它的问题是重复工作，不是答案错误。

下一步

重复信息暴露出来：标出被重新计算的状态

当前状态

当前结点、字符索引。

当前 Go 代码 · 高亮第 14 行

11/** Inserts a word into the trie. */12func (this *Trie) Insert(word string) {13	parent := this14	for _, ch := range word {15		if child, ok := parent.children[ch]; ok {16			parent = child17		} else {

优化方向：26 叉 Trie 结点带 isEnd;逐字符向下走或建。

04交互算法精讲

整体地图：先做什么，再做什么

1建模把输入翻译成“字符前缀路网”，明确答案需要观察什么。
2状态只维护当前结点、字符索引。
3转移每一步按照 26 叉 Trie 结点带 isEnd;逐字符向下走或建。
4收尾读取 search("apple") true。，并复核边界与复杂度。

05交互算法精讲

字符前缀路网：核心概念

节点表示前缀状态，结束标记区分完整单词与普通前缀。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：当前结点、字符索引。

核心不变量

• 从根到 isEnd 路径拼出单词。

动画 3 · 核心概念

建立“字符前缀路网”心智模型

用主例建立核心状态，先预测下一步，再公开正确分支和理由。

Step 1/30%

题目与输入建立输入、目标与算法心智

Trie:边标字符,结点标记单词结尾

正在加载算法场景...

发生了什么

实现 insert/search/startsWith 词典。

为什么

26 叉 Trie 结点带 isEnd;逐字符向下走或建。

下一步

根结点 children 为空：root = new TrieNode()

当前状态

当前结点、字符索引。

当前 Go 代码 · 高亮第 7 行

4}5 6/** Initialize your data structure here. */7func Constructor() Trie {8	return Trie{isWord: false, children: make(map[rune]*Trie)}9}10

06交互算法精讲

核心机制：状态如何一步步变化

要求实现一个 Trie 的数据结构，具有 `insert`, `search`, `startsWith` 三种操作这一题就是经典的 Trie 实现。本题的实现可以作为 Trie 的模板。

26 叉 Trie 结点带 isEnd;逐字符向下走或建。

执行过程中持续维护：当前结点、字符索引。

正确性依赖以下不变量：从根到 isEnd 路径拼出单词。

面试时可以压缩为：标准 Trie insert/search O(L)。

落到当前题，执行机制可以压缩为：26 叉 Trie 结点带 isEnd;逐字符向下走或建。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

动画 4 · 机制构建

一次状态转移为什么成立

集中观察一次选择、计算和状态写回，让变量变化与原因同时出现。

Step 1/50%

沿 'a' 下行,必要时新建结点walk / create child

插入 'apple':当前字符 'a'

正在加载算法场景...

发生了什么

逐字符建立路径。

为什么

前缀共享自动发生。

下一步

沿 'p' 下行,必要时新建结点：walk / create child

当前状态

path='a'。

当前 Go 代码 · 高亮第 13 行

10 11/** Inserts a word into the trie. */12func (this *Trie) Insert(word string) {13	parent := this14	for _, ch := range word {15		if child, ok := parent.children[ch]; ok {16			parent = child

07交互算法精讲

正确性证明：为什么不会漏答案

初始化

初始化：算法开始时，全部合法候选仍在状态表示范围内；从根到 isEnd 路径拼出单词。

保持

保持：执行“26 叉 Trie 结点带 isEnd;逐字符向下走或建。”时，只删除已经能证明不可能的候选，并把新信息写回当前结点、字符索引。

终止

终止：没有待处理状态或达到命中条件时，当前可观察结果就是“search("apple") true。”。

正确性抓手不是“样例跑通”，而是每一帧结束后仍能复述：从根到 isEnd 路径拼出单词。

08交互算法精讲

完整执行过程

1题目与输入实现 insert/search/startsWith 词典。因为：26 叉 Trie 结点带 isEnd;逐字符向下走或建。
2沿 'a' 下行,必要时新建结点逐字符建立路径。因为：前缀共享自动发生。
3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4沿 'l' 下行,必要时新建结点逐字符建立路径。因为：前缀共享自动发生。
5沿 'e' 下行,必要时新建结点逐字符建立路径。因为：前缀共享自动发生。
6'apple' 存在于 Trie精确匹配查找。因为：O(L) 路径长度。
7前缀 'app' 存在只走路径,不查 end。因为：前缀存在即可 true。
8收尾与复杂度search("apple") true。因为：时间 O(n) · 空间 O(1)。26 叉 Trie 结点带 isEnd;逐字符向下走或建。

动画 5 · 完整执行

从输入完整走到可观察结果

从主例第一帧运行到答案，时间轴始终显示当前状态、因果解释和下一步。

Step 1/80%

题目与输入建立输入、目标与算法心智

Trie:边标字符,结点标记单词结尾

正在加载算法场景...

发生了什么

实现 insert/search/startsWith 词典。

为什么

26 叉 Trie 结点带 isEnd;逐字符向下走或建。

下一步

沿 'a' 下行,必要时新建结点：walk / create child

当前状态

当前结点、字符索引。

当前 Go 代码 · 高亮第 7 行

4}5 6/** Initialize your data structure here. */7func Constructor() Trie {8	return Trie{isWord: false, children: make(map[rune]*Trie)}9}10

09交互算法精讲

把动画和 Go 代码逐行对应

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段，在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

动画 6 · 代码映射

让每个动作都落到 Go 分支

重新执行关键分支，只显示当前代码附近窗口，并说明这行为什么在此刻运行。

Step 1/60%

根结点 children 为空root = new TrieNode()

Trie:边标字符,结点标记单词结尾

正在加载算法场景...

发生了什么

准备执行操作序列。

为什么

共享前缀节省空间。

下一步

沿 'p' 下行,必要时新建结点：walk / create child

当前状态

空 Trie。

当前 Go 代码 · 高亮第 14 行

11/** Inserts a word into the trie. */12func (this *Trie) Insert(word string) {13	parent := this14	for _, ch := range word {15		if child, ok := parent.children[ch]; ok {16			parent = child17		} else {

10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法

type Trie struct {
	isWord   bool
	children map[rune]*Trie
}

/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{isWord: false, children: make(map[rune]*Trie)}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
	parent := this
	for _, ch := range word {
		if child, ok := parent.children[ch]; ok {
			parent = child
		} else {
			newChild := &Trie{children: make(map[rune]*Trie)}
			parent.children[ch] = newChild
			parent = newChild
		}
	}
	parent.isWord = true
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
	parent := this
	for _, ch := range word {
		if child, ok := parent.children[ch]; ok {
			parent = child
			continue
		}
		return false
	}
	return parent.isWord
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
	parent := this
	for _, ch := range prefix {
		if child, ok := parent.children[ch]; ok {
			parent = child
			continue
		}
		return false
	}
	return true
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */

最小测试集合

func main() {
    // 1. 主例
    //    输入：mode="implement-trie", words=["apple","app","april"]
    //    期望：search("apple") true。
    //
    // 2. 失败 / 未命中
    //    检查：Java 可用 HashMap 字符→结点。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC211 通配搜索；LC212 单词搜索 II
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

11交互算法精讲

正确性与复杂度

时间复杂度 O(n)

执行过程中只保留仍可能影响答案的状态。26 叉 Trie 结点带 isEnd;逐字符向下走或建。

空间复杂度 O(1)

额外状态主要用于维护：当前结点、字符索引。

终局不变量

• 从根到 isEnd 路径拼出单词。

12交互算法精讲

最容易写错的地方

错误 1

Java 可用 HashMap 字符→结点。

边界复查

必须额外检查空输入、单元素、未命中或不可达情况，以及恰好落在边界的输入。

13交互算法精讲

最后复盘：带走逻辑链

1题意实现 insert/search/startsWith 词典。
2重复逐个单词完整比较会重复扫描共同前缀；Trie 让共享前缀只建立和经过一次。
3优化26 叉 Trie 结点带 isEnd;逐字符向下走或建。
4证明从根到 isEnd 路径拼出单词。
5复杂度时间 O(n)，空间 O(1)

面试表达：标准 Trie insert/search O(L)。

迁移练习

• LC211 通配搜索
• LC212 单词搜索 II