购物车中没有产品。
211. 添加与搜索单词 – 数据结构设计（中等）
Blind 75 › 211. 添加与搜索单词 - 数据结构设计（中等） （第 2 章）
题目
设计一个词典数据结构：既能不断加入新单词，也能查询一个“可能带 . 通配符”的模式，是否与之前加入的某个单词匹配。
WordDictionary()：初始化词典对象。void addWord(word)：把word加进词典。bool search(word)：word只含小写字母或.；每个.能代表任意一个小写字母。若词典中存在与它匹配的单词则返回true，否则返回false。
自造示例：
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：当前节点是否恰好是某个完整单词的结尾。
addWord：从根节点出发，按字符逐层前进；缺少哪个子节点就新建；走完后把终点节点的isWord置为true。search：从根节点、下标0开始递归。- 普通字符：只走
children[c - 'a']这一条路。 .：遍历当前节点所有非空子节点，任一条分支成功就返回true。- 走到模式末尾时，必须返回当前节点的
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 个步骤串成流程，并逐步演示：
C++
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(本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。
还没有评论，来说两句？