LeetCode 211. 添加与搜索单词 - 数据结构设计
目录
题目描述
题意分析
需要设计一个支持两种操作的容器：
addWord把一个单词存进去，search判断是否存在一个已存过的单词能与给定模式串完全匹配，模式串里可能出现.，一个.恰好匹配任意一个小写字母。关键在于「完全匹配」而不是「前缀匹配」，长度必须相等，所以
.不能吞掉多个字符，也不能匹配空。字符集只有 26 个小写字母，单词长度不超过 25，
addWord和search合计最多调用 10^4 次，其中带.的查询保证最多含 2 个.。字符集小且固定，暗示每个节点可以用定长 26 的数组而不是哈希表来存孩子；.的数量被限制住，暗示在.处做分叉枚举是被出题人允许的开销。边界包括：同一个单词被重复添加、模式串全是
.、模式串比库中所有单词都长或都短、以及在还没添加任何单词时就查询。
解法：Trie + DFS
核心思路
暴力做法是把所有单词存进一个列表，每次
search遍历列表逐个做「同长度且逐位匹配，.位跳过」的比较。这是对的，但每次查询要扫全部单词，总代价是「单词数 × 单词长度」，在 10^4 次查询下退化成千万次字符比较，瓶颈在于不同单词的公共前缀被反复重新比较了无数遍。观察点是：所有单词按字符逐位展开后，公共前缀天然共享同一条路径。如果把单词组织成一棵以字符为边的树，那么「按位比较」就变成「沿边下沉」，一次下沉同时代表了所有共享该前缀的单词，公共前缀的重复比较被彻底消掉。
.的存在让匹配不再是唯一路径，而是从当前节点出发的一次分叉。但分叉只发生在.所在的这一层，且分支数被字符集大小 26 卡死，因此变成一个可控的深度优先搜索。数据结构不变量：树上从根到任意节点的边序列，恰好是某个已添加单词的一个前缀；节点上的布尔标记
isEnd为真，当且仅当从根到该节点的边序列本身是一个被完整添加过的单词。有了这条不变量，「完全匹配」就等价于「沿着模式串走满全部字符后，落点节点的isEnd为真」。递归函数的语义固定为：
dfs(pos, node)返回「以node为根的子树中，是否存在一条路径能匹配模式串从下标pos到末尾的这一段」。这个返回值含义在空节点、走到串尾、普通字符、通配符四种情况下必须完全一致。
解题步骤
- 定义节点结构：一个长度 26 的孩子指针数组加一个
isEnd布尔位。之所以用定长数组而不是哈希表，是因为字符集固定，数组下标c - 'a'的定位是无分支的常数操作，且在.分叉时可以直接顺序枚举 26 个槽位，代码比遍历哈希表的 entry 更短更稳。addWord从根出发逐字符下沉，孩子为空就新建节点，走完全部字符后把落点的isEnd置真。之所以只在末尾置真而不在中途置真，是因为isEnd承担的正是「这里是一个完整单词的终点」这一唯一语义，中途置真会让"apple"的前缀"app"被误判为已存在。search直接调用dfs(word, 0, root)，把所有逻辑收进递归。之所以不写迭代，是因为.会产生分叉，迭代需要手动维护栈，而分叉深度天然对应递归深度，递归写法更贴合问题结构。dfs的第一件事是判空节点返回false。之所以要判，是因为普通字符分支会直接把node.next[c - 'a']传下去而不做检查，把空指针的处理统一收拢到函数入口，比在每个调用点各写一次判断更不容易漏。dfs的第二件事是判pos == word.length()时返回node.isEnd。之所以返回isEnd而不是true，正是「完全匹配」与「前缀匹配」的分水岭：模式串走完了，但当前节点未必是某个单词的终点。- 遇到
.时枚举 26 个孩子，任一非空孩子的dfs(pos + 1, child)为真就立刻返回真。之所以能短路返回，是因为题目只问存在性，找到一条可行路径后其余分支的结果不影响答案。- 遇到普通字符时只递归唯一确定的那个孩子。之所以不需要循环，是因为普通字符把分支因子压回 1，这也是为什么
.的个数才是复杂度的主导因素。以调用序列
addWord("bad")、addWord("dad")、addWord("mad")、search("pad")、search(".ad")走一遍。三次添加后，根节点的b、d、m三个槽位各挂一棵深度为 3 的链，三条链的末端节点isEnd都为真。
search("pad")：dfs(0, root)，pos = 0不等于 3，字符p不是.，取root.next['p' - 'a']，这个槽从未被写过，为空，递归进入后在入口判空返回false，整个查询返回false，符合预期。
search(".ad")：dfs(0, root)，字符是.，进入枚举。下标 1 对应b，孩子非空，递归dfs(1, b节点)；pos = 1，字符a非通配，取b节点.next['a' - 'a']，非空，递归dfs(2, ba节点)；字符d，取ba节点.next['d' - 'a']，非空，递归dfs(3, bad节点)；pos = 3等于串长，返回该节点的isEnd，为真。真值沿调用链一路短路返回，.的枚举在第一个命中的分支就停下，不再试d和m，最终返回true。
代码实现
class WordDictionary {
private final TrieNode root = new TrieNode();
public WordDictionary() {
}
public void addWord(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
int idx = word.charAt(i) - 'a';
if (node.next[idx] == null) {
node.next[idx] = new TrieNode();
}
node = node.next[idx];
}
node.isEnd = true;
}
public boolean search(String word) {
return dfs(word, 0, root);
}
private boolean dfs(String word, int pos, TrieNode node) {
if (node == null) {
return false;
}
if (pos == word.length()) {
return node.isEnd;
}
char c = word.charAt(pos);
if (c == '.') {
for (TrieNode child : node.next) {
if (child != null && dfs(word, pos + 1, child)) {
return true;
}
}
return false;
}
return dfs(word, pos + 1, node.next[c - 'a']);
}
private static class TrieNode {
TrieNode[] next = new TrieNode[26];
boolean isEnd;
}
}
type WordDictionary struct {
root *TrieNode
}
type TrieNode struct {
next [26]*TrieNode
isEnd bool
}
func Constructor() WordDictionary {
return WordDictionary{root: new(TrieNode)}
}
func (w *WordDictionary) AddWord(word string) {
node := w.root
for i := 0; i < len(word); i++ {
idx := word[i] - 'a'
if node.next[idx] == nil {
node.next[idx] = &TrieNode{}
}
node = node.next[idx]
}
node.isEnd = true
}
func (w *WordDictionary) Search(word string) bool {
var dfs func(int, *TrieNode) bool
dfs = func(pos int, node *TrieNode) bool {
if node == nil {
return false
}
if pos == len(word) {
return node.isEnd
}
c := word[pos]
if c == '.' {
for i := 0; i < 26; i++ {
if node.next[i] != nil && dfs(pos+1, node.next[i]) {
return true
}
}
return false
}
return dfs(pos+1, node.next[c-'a'])
}
return dfs(0, w.root)
}
复杂度分析
- 时间复杂度：
addWord为 $O(L)$，因为只是沿着 $L$ 个字符各下沉一层；search为 $O(26^k \cdot L)$，其中 $L$ 是模式串长度、$k$ 是其中.的个数，凭据是普通字符处分支因子恒为 1，只有.处会把当前搜索状态扩展成至多 26 个，$k$ 个通配符叠乘就得到这个上界，题目限定 $k \le 2$ 时实际只有常数倍开销。- 空间复杂度：$O(26 \cdot N)$，其中 $N$ 是所有已添加单词的字符总数，凭据是每插入一个新字符最多新建一个节点，而每个节点固定持有 26 个孩子指针；递归栈深度不超过模式串长度 $L$，被节点开销吸收。
关键点总结
- 「多个字符串共享前缀」这个信号出现时，应该立刻想到把线性容器换成前缀树，把重复的前缀比较折叠成一次路径下沉，这是所有前缀类题目的通用第一步。
isEnd标记是区分「前缀存在」和「单词存在」的唯一手段，任何基于前缀树的设计题都必须先想清楚这个标记放在哪、由谁置位、被谁读取。- 递归函数的返回值语义必须一次性定死并在所有分支保持一致，本题定为「子树内能否匹配剩余模式段」，空节点、串尾、通配、普通四个分支才能各自独立地写正确。
- 把空指针检查上提到递归入口，而不是分散在每个调用点，能显著减少分支遗漏，这在树和图的 DFS 里是可以稳定复用的写法。
- 分支因子的来源要单独识别：本题只有
.会制造分叉，识别出这一点后复杂度分析和优化方向都变得清晰，同样的思路可用于任何「带通配的匹配」问题。- 面试视角：面试官期待你先说清朴素列表存储的瓶颈在哪，再主动提出前缀树，然后当场把
.的处理定位为「唯一的分叉点」并给出 $26^k$ 的估计。如果被追问优化，可以提「按长度分桶后再建树」或「记录每层最长单词长度以提前剪枝」，但不必真的写出来。
易错点总结
- 在
pos == word.length()处直接return true：用例先addWord("apple")再search("app")，会错误返回true，因为把前缀当成了完整单词，必须返回node.isEnd。- 普通字符分支不判空就解引用，例如写成
return dfs(word, pos + 1, node.next[c - 'a'].xxx)或在调用前访问孩子字段：用例search("pad")而库中只有"bad"，root.next['p'-'a']为null，会直接抛空指针异常。.分支枚举孩子时写成for (TrieNode child : node.next) return dfs(...)，只试第一个非空孩子就返回：用例addWord("bad")、addWord("mad")、search(".ad")在字典只含"mad"时会返回false，因为遇到空槽或首个失败分支就提前结束，必须遍历完所有 26 个槽才能返回false。.分支中把子递归的false也当成最终结果返回，例如return dfs(word, pos + 1, child)写在循环体内：用例addWord("bad")、addWord("dad")、search(".ad")，先试到b失败就整体返回false，漏掉了后面能匹配的d分支。- 在
addWord的循环中途给每个经过的节点都置isEnd = true：用例addWord("bad")后search("ba")会返回true，把所有前缀都变成了合法单词。- 把
.当作可匹配零个或多个字符处理：用例addWord("bad")、search(".")，会错误返回true，而正确答案是false，因为一个.只匹配恰好一个字符。- 忘记为每次
search重新从root开始，而是复用了上一次查询结束时的节点指针：用例连续search("bad")、search("mad")，第二次会从bad的末端继续下沉，必然返回false。- 用
HashMap<Character, TrieNode>存孩子却在.分支里遍历'a'到'z'并对不存在的键调用get后直接使用：用例任何含.的查询，返回的null未判空会抛异常；用定长数组则天然把「不存在」表示为null槽位。- Go 版本把
next声明成[]*TrieNode但没有make初始化：用例第一次AddWord("bad")，对 nil 切片按下标赋值会 panic，声明成数组[26]*TrieNode才是零值可用的。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 208. 实现 Trie (前缀树) | 中等 | 无通配的基础版，只需迭代下沉，重点是区分 search 与 startsWith
|
| 212. 单词搜索 II | 困难 | 把前缀树挂到网格回溯上，考察边搜索边剪枝与命中后摘除节点 |
| 648. 单词替换 | 中等 | 求最短匹配前缀，下沉过程中一旦遇到 isEnd 就立即停止 |
| 677. 键值映射 | 中等 | 节点上存的是数值而非布尔，需要处理同键覆盖时的差值更新 |
| 720. 词典中最长的单词 | 中等 | 要求路径上每个前缀都是合法单词，遍历时需沿 isEnd 链推进 |