今天和大家聊的问题叫做 添加与搜索单词，我们先来看题面：https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/
Design a data structure that supports adding new words and finding if a string matches any previously added string.
题意
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 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"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True 提示： 1 <= word.length <= 500 addWord 中的 word 由小写英文字母组成 search 中的 word 由 '.' 或小写英文字母组成 最多调用 50000 次 addWord 和 search
解题
用字典树来作为存储的数据结构。新增单词的时候，就使用字典树插入新单词的方法。在查找某一个字典树时，使用深度优先搜索即可。
class WordDictionary { public: //定义字典树中每个节点的结构 struct Node{ bool isword = false; //用于标记当前节点是否为单词的最后一个字符 Node* next[27] = {}; }; Node* root; //每一个class都有一棵字典树 /** Initialize your data structure here. */ WordDictionary() { root = new Node(); //新建一棵字典树 } /** Adds a word into the data structure. */ void addWord(string word) { Node* tmp = root; for(auto w: word){ if(tmp->next[w - 'a'] == NULL){ //还没有这个节点 Node* tt = new Node(); tmp->next[w - 'a'] = tt; //那就新建节点 } tmp = tmp->next[w - 'a']; } tmp->isword = true; //遍历完一个单词 } /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */ bool search(string word) { return dfs(word, root, 0); } bool dfs(string word, Node* root, int i){ if(!root) return false; if(i >= word.size()) return root->isword; //看看是不是一个完整的单词 if(word[i] != '.'){ if(root->next[word[i] - 'a']){ return dfs(word, root->next[word[i] - 'a'], i+1); } else return false; } for(auto t: root->next){ if(t){ if(dfs(word, t, i+1)) return true; } } return false; } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
