1、思路

在已有的 前缀树 基础上实现魔法字典。

注意在做search操作时有且只有一种情况返回true：这是一个存在于前缀树中的完整单词，并且恰好经过了一次字母变换。

2、代码

class MagicDictionary {
private:
    struct TrieNode                                 //前缀树结构体
    {
        bool isWord;
        vector<shared_ptr<TrieNode>> children;
        TrieNode() : isWord(false), children(26, nullptr){}
    };

    shared_ptr<TrieNode> root;

public:
    MagicDictionary() {
        root = make_shared<TrieNode>();             //初始化前缀树
    }

    void buildDict(vector<string> dictionary) {     //将单词逐个插入前缀树
        for (string& s : dictionary)
        {
            auto node = root;
            for (char& ch : s)
            {
                if (node->children[ch - 'a'] == nullptr)
                {
                    node->children[ch - 'a'] = make_shared<TrieNode>();
                }
                node = node->children[ch - 'a'];
            }

            node->isWord = true;                    //标记单词结尾
        }
    }

    bool search(string searchWord) {
        return dfs(root, searchWord, 0, 0);
    }

    // dfs 查找是否存在该魔法单词
    bool dfs(shared_ptr<TrieNode> root, string searchWord, int i, int edit)
    {
        if (root == nullptr) return false;
        //唯一返回 true 的情况
        if (root->isWord && i == searchWord.length() && edit == 1) return true;

        if (i < searchWord.length() && edit <= 1)
        {
            bool found = false;
            for (int j = 0; j < 26 && !found; ++ j)     //把26个字母全遍历一遍
            {
                //相同的那个字母会让 edit 保持不变，另外 25 个字母会让 edit 增加 1
                int nextEdit = j == searchWord[i] - 'a' ? edit : edit + 1;
                found = dfs(root->children[j], searchWord, i + 1, nextEdit);
            }

            return found;
        }

        return false;
    }
};