211. 添加与搜索单词 – 数据结构设计（中等）

Blind 75 › 211. 添加与搜索单词 - 数据结构设计（中等） （第 2 章）
文章工具

题目

设计一个词典数据结构：既能不断加入新单词，也能查询一个“可能带 . 通配符”的模式，是否与之前加入的某个单词匹配。

  • WordDictionary()：初始化词典对象。
  • void addWord(word)：把 word 加进词典。
  • bool search(word)：word 只含小写字母或 .；每个 . 能代表任意一个小写字母。若词典中存在与它匹配的单词则返回 true，否则返回 false。

自造示例：

C++ 片段需补全 main() 函数才能运行在实训台打开 →
WordDictionary wd;
wd.addWord("cat");
wd.addWord("car");
wd.addWord("dot");
wd.search("cat");  // true：精确命中
wd.search("c.t");  // true：c-a-t，点匹配 a
wd.search("..r");  // true：c-a-r
wd.search("do");   // false：d-o 只是某个词的前缀，不是完整词
wd.search(".a.");  // true：cat 与 car 都匹配

约束：单词长度 1 ≤ word.length ≤ 25；addWord 只含小写字母；search 含 . 或小写字母；两类调用合计最多 104 次。

思路

一句话：用前缀树（Trie）把已加入的单词存成树，查询时普通字母走唯一路径，遇到 . 就递归尝试所有存在的分支。

最直白的做法：每次 search 都拿当前模式，和词典里所有单词逐个字符比较。加入单词很快，但查询每次要扫过全部单词；最坏 104 次查询、每次比较 104 × 25 个字符，约为 2.5 × 109 次比较，明显会超时。

关键观察：如果没有 .，这就是“字典里有没有某个完整单词”，Trie 可以沿前缀一路走，一次 O(长度) 完成。加了 . 后，普通字符仍然只能走唯一一个子节点；只有遇到 . 时才产生分叉。更妙的是，Trie 只会沿着真实存在的字母分支走下去，前缀一旦不存在就立刻剪掉，不需要枚举 26长度 个字符串。

因此选 Trie + 递归回溯：插入负责建树，查询负责在树上 DFS。

解法

每个节点保存两个信息：

  • children：从当前前缀出发，下一个字符能走到哪些子节点（本题只含小写字母，最多 26 个）。
  • isWord：当前节点是否恰好是某个完整单词的结尾。
  1. addWord：从根节点出发，按字符逐层前进；缺少哪个子节点就新建；走完后把终点节点的 isWord 置为 true。
  2. search：从根节点、下标 0 开始递归。
  3. 普通字符：只走 children[c - 'a'] 这一条路。
  4. .：遍历当前节点所有非空子节点，任一条分支成功就返回 true。
  5. 走到模式末尾时，必须返回当前节点的 isWord，而不是直接 true。

以自造数据为例：

操作Trie 中的路径结果
addWord(“cat”)根 → c → a → t，t 标记词尾—
addWord(“car”)复用 c、a，再新建 r，r 标记词尾—
addWord(“dot”)根 → d → o → t，t 标记词尾—
search(“c.t”)c → a，然后 . 尝试子节点 t，命中词尾true
search(“do”)d → o，到达时不是词尾false
search(“..r”)根分支 c，再分支 a，最后 r 命中词尾true

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

211. 添加与搜索单词 – 数据结构设计（中等） 解法步骤流程图
图① 解法步骤流程图（共 5 步）。
211. 添加与搜索单词 – 数据结构设计（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class TrieNode {
public:
 TrieNode* children[26] = {};
 bool isWord = false;
};  class WordDictionary {
 TrieNode* root;  bool dfs(TrieNode* node, const string& word, int idx) {
 if (!node) return false;
 if (idx == word.size()) return node->isWord;  char ch = word[idx];
 if (ch == '.') {
 for (TrieNode* child : node->children) {
 if (child && dfs(child, word, idx + 1)) return true;
 }
 return false;
 }
 return dfs(node->children[ch - 'a'], word, idx + 1);
 }  public:
 WordDictionary() : root(new TrieNode()) {}  void addWord(
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。