C++刷leetcode（676. 实现一个魔法字典）【字典树】【深度优先搜索】

糖逗

题目描述：

1. 实现一个带有buildDict, 以及 search方法的魔法字典。
   
2. 
   
3. 对于buildDict方法，你将被给定一串不重复的单词来构建一个字典。
   
4. 
   
5. 对于search方法，你将被给定一个单词，并且判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
   
6. 
   
7. 示例 1:
   
8. 
   
9. Input: buildDict(["hello", "leetcode"]), Output: Null
   
10. Input: search("hello"), Output: False
    
11. Input: search("hhllo"), Output: True
    
12. Input: search("hell"), Output: False
    
13. Input: search("leetcoded"), Output: False
    
14. 注意:
    
15. 
    
16. 你可以假设所有输入都是小写字母 a-z。
    
17. 为了便于竞赛，测试所用的数据量很小。你可以在竞赛结束后，考虑更高效的算法。
    
18. 请记住重置MagicDictionary类中声明的类变量，因为静态/类变量会在多个测试用例中保留。 请参阅这里了解更多详情。

复制代码

1. class MagicDictionary {
   
2. private:
   
3.     bool isEnd;
   
4.     MagicDictionary* next[26];
   
5. public:
   
6.     /** Initialize your data structure here. */
   
7.     MagicDictionary() {
   
8.         isEnd = false;
   
9.         memset(next, 0, sizeof(next));
   
10. 
    
11.     }
    
12.    
    
13.     /** Build a dictionary through a list of words */
    
14.     void buildDict(vector<string> dict) {
    
15.         for(auto cha : dict){
    
16.             MagicDictionary* node = this; //注意这块儿的书写！！！！！！！！
    
17.             for(auto cha1 : cha){
    
18.                 if(node -> next[cha1 - 'a'] == NULL){
    
19.                     node -> next[cha1 - 'a'] = new MagicDictionary();
    
20.                 }
    
21.                 node = node -> next[cha1 - 'a'];
    
22.             }
    
23.             node -> isEnd = true;
    
24.         }
    
25.     }
    
26.    
    
27.     /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    
28.     void dfs(bool& res, string& word, MagicDictionary* cur, int sum, int step){
    
29.         if(sum > 1 || step > word.size()) return;
    
30.         if(step == word.size()){
    
31.             if(sum == 1 && cur -> isEnd) res = true;
    
32.             return;
    
33.         }
    
34.         for(int i = 0; i < 26; i++){
    
35.             MagicDictionary* temp = cur;//注意这块儿的书写！！！！！！！！
    
36.             if(temp -> next[i] != NULL){
    
37.                 temp = temp -> next[i];
    
38.                 if(i != word[step] - 'a'){
    
39.                     dfs(res, word, temp, sum + 1, step + 1);//注意这块儿的书写！！！！！！！！
    
40.                 }else{
    
41.                     dfs(res, word, temp, sum, step + 1);
    
42.                 }
    
43.             }
    
44.         }
    
45.     }
    
46.     bool search(string word) {
    
47.         bool res = false;
    
48.         MagicDictionary* node = this;
    
49.         dfs(res, word, node, 0, 0);
    
50.         return res;
    
51.     }
    
52. };
    
53. 
    
54. /**
    
55. * Your MagicDictionary object will be instantiated and called as such:
    
56. * MagicDictionary* obj = new MagicDictionary();
    
57. * obj->buildDict(dict);
    
58. * bool param_2 = obj->search(word);
    
59. */

复制代码

糖逗

注意递归的书写格式，以及树的初始化存储。

糖逗

掉了好多坑，总算想明白了这道题