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

糖逗

题目描述：

实现一个带有buildDict, 以及 search方法的魔法字典。

对于buildDict方法，你将被给定一串不重复的单词来构建一个字典。

对于search方法，你将被给定一个单词，并且判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

示例 1:

Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False
注意:

你可以假设所有输入都是小写字母 a-z。
为了便于竞赛，测试所用的数据量很小。你可以在竞赛结束后，考虑更高效的算法。
请记住重置MagicDictionary类中声明的类变量，因为静态/类变量会在多个测试用例中保留。 请参阅这里了解更多详情。

class MagicDictionary {
private:
    bool isEnd;
    MagicDictionary* next[26];
public:
    /** Initialize your data structure here. */
    MagicDictionary() {
        isEnd = false;
        memset(next, 0, sizeof(next));

    }
    
    /** Build a dictionary through a list of words */
    void buildDict(vector<string> dict) {
        for(auto cha : dict){
            MagicDictionary* node = this; //注意这块儿的书写！！！！！！！！
            for(auto cha1 : cha){
                if(node -> next[cha1 - 'a'] == NULL){
                    node -> next[cha1 - 'a'] = new MagicDictionary();
                }
                node = node -> next[cha1 - 'a'];
            }
            node -> isEnd = true;
        }
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    void dfs(bool& res, string& word, MagicDictionary* cur, int sum, int step){
        if(sum > 1 || step > word.size()) return;
        if(step == word.size()){
            if(sum == 1 && cur -> isEnd) res = true;
            return;
        }
        for(int i = 0; i < 26; i++){
            MagicDictionary* temp = cur;//注意这块儿的书写！！！！！！！！
            if(temp -> next[i] != NULL){
                temp = temp -> next[i];
                if(i != word[step] - 'a'){
                    dfs(res, word, temp, sum + 1, step + 1);//注意这块儿的书写！！！！！！！！
                }else{
                    dfs(res, word, temp, sum, step + 1);
                }
            } 
        }
    }
    bool search(string word) {
        bool res = false;
        MagicDictionary* node = this;
        dfs(res, word, node, 0, 0);
        return res;
    }
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dict);
 * bool param_2 = obj->search(word);
 */

糖逗

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

糖逗

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