leetcode做题笔记211. 添加与搜索单词

单词"/>

leetcode做题笔记211. 添加与搜索单词

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

实现词典类 WordDictionary ：

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

示例：

输入：
["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

思路一：前缀树

class WordDictionary {
public:struct dictTreeNode{bool isend;dictTreeNode* next[26];dictTreeNode() : isend(false){for(int i = 0;i < 26;i++) next[i] = NULL;}};dictTreeNode* root;WordDictionary() {root = new dictTreeNode();}void addWord(string word) {dictTreeNode* tr = root;for(int i = 0;i < word.size();i++){if(tr->next[word[i] - 'a'] == NULL){tr->next[word[i] - 'a'] = new dictTreeNode();}tr = tr->next[word[i] - 'a']; }tr->isend = true;}bool searchrecur(string& word,dictTreeNode* tr,int index){if(index == word.size()) return tr->isend;for(int i = index;i < word.size();i++){if(word[i] == '.'){for(int j = 0;j < 26;j++){if(tr->next[j] == NULL) continue;if(searchrecur(word,tr->next[j],i + 1)) return true;}return false;}if(tr->next[word[i] - 'a'] == NULL){return false;}tr = tr->next[word[i] - 'a']; }return tr->isend;}bool search(string word) {return searchrecur(word,root,0);}
};/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary* obj = new WordDictionary();* obj->addWord(word);* bool param_2 = obj->search(word);*/

分析：

本题有关字典的数据结构设计，注意到字典与之前的前缀树的思路很像，将前缀树的方法重新编写，当搜索的时候需要不断向后匹配看是否与存储的单词相同，最后返回bool

总结：

本题为前缀树相关问题，改写前缀树的方法即可解决问题