LeetCode 面试经典 150_字典树_添加与搜索单词 - 数据结构设计（96_211_C++

LeetCode 面试经典 150_字典树_添加与搜索单词 - 数据结构设计（96_211_C++_中等）

- 题目描述：
- 输入输出样例：
- 题解：
- - 解题思路：
  - - 思路一（字典树）：
  - 代码实现
  - - 代码实现（思路一（字典树））：

题目描述：

请你设计一个数据结构，支持添加新单词和查找字符串是否与任何先前添加的字符串匹配。

实现词典类 WordDictionary ：

WordDictionary() 初始化词典对象
void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word
中可能包含一些 ‘.’ ，每个 . 都可以表示任何一个字母。

输入输出样例：

示例 1：
输入：
[“WordDictionary”,“addWord”,“addWord”,“addWord”,“search”,“search”,“search”,“search”]
[[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[“.ad”],[“b…”]]
输出：
[null,null,null,null,false,true,true,true]
解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord(“bad”);
wordDictionary.addWord(“dad”);
wordDictionary.addWord(“mad”);
wordDictionary.search(“pad”); // 返回 False
wordDictionary.search(“bad”); // 返回 True
wordDictionary.search(“.ad”); // 返回 True
wordDictionary.search(“b…”); // 返回 True

提示：
1 <= word.length <= 25
addWord 中的 word 由小写英文字母组成
search 中的 word 由 ‘.’ 或小写英文字母组成
最多调用 10⁴次 addWord 和 search

题解：

解题思路：

思路一（字典树）：

1、实现思路如下
插入单词：

从左到右插入这个单词的每个字母，若当前字母不存在字典树中（注意child是0~25，若child为nullptr则不存在），创建结点
若为最后一个单词则进行标记isEnd=true。

查找单词：
因单词中包含’.',所以我们要分两种情况讨论，从左到右查找这个单词的每个字符。

若当前位置为字母，则查找node[word[i]-‘a’]存不存在，若存在则继续查找，若不存在则返回false
若当前位置为’.',我们需要挨个判断此节点的所有儿子结点的分支。首先此节点的儿子结点不能为nullptr，其次递归的匹配其儿子结点，若匹配成功则返回true，否则返回false

需要非常注意一点字典树的根结点不存储任何信息。

2、复杂度分析：
① 时间复杂度：O(26^k·L），假设在最坏情况下字典树的每个节点都有26个子节点，如果遇到个 “.”，则为每个.都会进行 26 次递归。
② 空间复杂度：O(N×L)，O(N×L)，其中 N 是独立单词的数量，L 是单词的平均长度。

代码实现

代码实现（思路一（字典树））：

classWordDictionary{private:// 定义字典树的节点结构体（TrieNode）structTrieNode{vector<TrieNode*>child;// 子节点数组，表示26个字母的子节点boolisEnd;// 标记当前节点是否为某个单词的结束节点TrieNode():child(26,nullptr),isEnd(false){}// 构造函数，初始化子节点数组为26个nullptr，并将isEnd初始化为false};TrieNode*root;// 根节点// 插入单词的函数voidinsert(TrieNode*root,conststring&word){TrieNode*node=root;// 遍历单词中的每个字符for(autoc:word){// 计算字符对应的索引，并检查当前字符的子节点是否为空if(node->child[c-'a']==nullptr){// 如果为空，说明该字符路径还没有建立，创建新的节点node->child[c-'a']=newTrieNode();}// 将当前节点指向下一个字符的子节点node=node->child[c-'a'];}// 单词遍历完成后，将当前节点的isEnd标记为true，表示这是一个完整的单词node->isEnd=true;}// 搜索单词的深度优先搜索（DFS）函数booldfs(string&word,TrieNode*node,intindex){// 如果遍历到单词的末尾，返回当前节点是否为单词的结束节点if(index==word.size()){returnnode->isEnd;}// 如果当前字符是'.'，可以匹配任意字符if(word[index]=='.'){// 遍历当前节点的所有子节点for(auto&child:node->child){// 对每个非空子节点递归进行DFSif(child!=nullptr&&dfs(word,child,index+1)){returntrue;// 如果某个子节点匹配成功，返回true}}returnfalse;// 如果所有子节点都无法匹配，返回false}else{// 如果当前字符不是'.'，则检查当前节点对应字符的子节点是否为空if(node->child[word[index]-'a']==nullptr){returnfalse;// 如果没有对应的子节点，返回false}// 否则继续递归搜索下一个字符returndfs(word,node->child[word[index]-'a'],index+1);}}public:// 构造函数，初始化根节点WordDictionary(){root=newTrieNode();}// 添加一个单词到字典中voidaddWord(string word){insert(root,word);// 调用插入函数}// 搜索单词（支持'.'通配符）boolsearch(string word){returndfs(word,root,0);// 从根节点开始递归DFS}};