链接：https://leetcode.cn/problems/implement-magic-dictionary/solution/by-xun-ge-v-3c60/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

本题为前缀树和dfs的一个结合
求解字符串s(searchWord)在另外一个字典集d(dictionary)中相关操作都可以运用
前缀树https://leetcode.cn/problems/implement-trie-prefix-tree/solution/chun-c-by-xun-ge-v-vnt5/
进行优化，力扣也有关于前缀树实现的习题，对前缀树不了解的可以进链接

前缀树：前缀树是一种用于快速检索的多叉树结构，利用字符串的公共前缀来降低查询时间，核心思想是空间换时间，经常被搜索引擎用于文本词频统计。
    typedef struct MagicDictionary{
        bool logo;//true表示字符串结束,false表示字符未结束
        struct MagicDictionary * next[26];
    } MagicDictionary; 
其中前缀树中每一个节点代表一个字符，以一个节点进行深度优先搜索，一直到末尾，那么经过的路径就为字典集中的一个字符串
具体实现
先对字典集d进行优化，转换为对应的前缀树，将所有的d子串存入字典树中，方便后续检索；
设计递归函数dfs(MagicDictionary * obj, char * searchWord, int inode, int len, int x)，searchWord其中为待检索的字符串，inode为当前处理到字符串 s 的哪一位，obj为当前搜索到字典树的索引编号，x为当前剩余的替换字符次数，根据题意，x固定为 1，含义为必须替换掉 s 的一个字符。
对于s而言，我们可以枚举新字符串在当前位置是何种字符（i = 26个选择），若当前枚举到的字符与 s[inode] 一致，则不消耗替换次数。
递归过程中替换次数为负数直接剪枝，当递归到字符串s结尾位置，检查是否位于前缀树末尾，并且x为0

代码

//前缀树 + 递归 + 深度优先搜索
typedef struct MagicDictionary{
    bool logo;//true表示字符串结束,false表示字符未结束
    struct MagicDictionary * next[26];
} MagicDictionary; 

//初始化
MagicDictionary* magicDictionaryCreate() {
    MagicDictionary * obj = malloc(sizeof(MagicDictionary));
    for(int i = 0; i < 26; i++)
    {
        obj->next[i] = NULL;
    }
    obj->logo = false;
    return obj;    
}
//转换前缀树
void magicDictionaryBuildDict(MagicDictionary* obj, char ** dictionary, int dictionarySize) {
    if(dictionarySize > 1)
    {
        magicDictionaryBuildDict(obj, dictionary, dictionarySize - 1);
    }
    int len = strlen(dictionary[dictionarySize-1]);
    for(int i = 0; i < len; i++)
    {
        if(obj->next[dictionary[dictionarySize-1][i] - 'a'] == NULL)
        {
            MagicDictionary * n = magicDictionaryCreate();
            obj->next[dictionary[dictionarySize-1][i] - 'a'] = n;
        }
        obj = obj->next[dictionary[dictionarySize-1][i] - 'a'];
    }
    obj->logo = true;
}
//递归判断字符串在字典树的情况
bool dfs(MagicDictionary * obj, char * searchWord, int inode, int len, int x)
{
    if(x < 0)//剪枝
    {
        return false;
    }
    if(inode == len)//到字符串末尾了，判断一下是否换了一个字符，是不是在字典集中存在完整的字符串
    {
        if(x == 0 && obj->logo == true)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    for(int i = 0; i < 26; i++)//寻找同层前缀树中存在的元素
    {
        if(obj->next[i])//存在
        {
            if(i == (searchWord[inode] - 'a'))//是不是和目标元素一样
            {
                if(dfs(obj->next[i], searchWord, inode+1, len, x) == true)
                {
                    return true;
                }
            }   
            else//不一样，修改次数-1，继续
            {
                if(dfs(obj->next[i], searchWord, inode+1, len, x-1) == true)
                {
                    return true;
                }
            }
        }
        
    }
    return false;//前缀树遍历完了，没有字符串和s字符串匹配
}

//调用dfs函数深度优先搜索
bool magicDictionarySearch(MagicDictionary* obj, char * searchWord) {
    int len = strlen(searchWord);
    return dfs(obj, searchWord, 0, len, 1);
}
//销毁前缀树
void magicDictionaryFree(MagicDictionary* obj) {
    for(int i = 0; i < 26; i++)
    {
        if(obj->next[i])
        {
            magicDictionaryFree(obj->next[i]); 
        }
    }
    free(obj);
}

/**
 * Your MagicDictionary struct will be instantiated and called as such:
 * MagicDictionary* obj = magicDictionaryCreate();
 * magicDictionaryBuildDict(obj, dictionary, dictionarySize);
 
 * bool param_2 = magicDictionarySearch(obj, searchWord);
 
 * magicDictionaryFree(obj);
*/

时间空间复杂度