class Solution
{
public:
    unordered_map<string, vector<string>> tree; // 构建图
    vector<vector<string>> ans;                 // 存放最终结果

    void dfs(vector<string> &cur, string curWord, string endWord)
    {
        if (curWord == endWord)
        {
            ans.push_back(cur);
            return;
        }
        for (string s : tree[curWord])
        {
            cur.push_back(s);
            dfs(cur, s, endWord);
            cur.pop_back();
        }
    }

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList)
    {
        if (wordList.size() == 0 || find(wordList.begin(), wordList.end(), endWord) == wordList.end())
            return {};
        unordered_set<string> bfsFromBegin{beginWord};                // 自顶向下的BFS队列 !!!注意使用集合
        unordered_set<string> bfsFromEnd{endWord};                    // 自底向上的BFS队列 !!!注意使用集合
        unordered_set<string> dirc(wordList.begin(), wordList.end()); // 初始化字典 记录未被访问过的字符串 !!!注意初始化方式
        bool findFlag = false, reverseFlag = false;                   // findFlag两队列是否存在相同的元素 reverseflag时刻标记当前BFS遍历的方向（false为自顶向下，true为自底向上）
        while (!bfsFromBegin.empty())
        {
            unordered_set<string> next;   // 存放下一层需要遍历的节点（由于此处BFS的特殊性【一次性扩展所有节点】，所以不是直接添加到原先队列的末尾，而是借助next）
            for (string s : bfsFromBegin) // 遍历过的节点从set中删除 避免成环
                dirc.erase(s);
            for (string s1 : bfsFromBegin)
            { // 扩展下一层的节点
                for (int i = 0; i < s1.size(); ++i)
                {
                    string s2 = s1; // s2记录由s1扩展而来字符串 !!!注意这条语句不要放错位置
                    for (char c = 'a'; c <= 'z'; ++c)
                    {
                        s2[i] = c;
                        if (dirc.count(s2) == 0)
                            continue;
                        if (bfsFromEnd.count(s2))
                        {
                            findFlag = true; // 找到双向BFS重合的字符串，BFS过程即可终止
                        }
                        else
                        {
                            next.insert(s2); // 将字符串加入扩展队列
                        }
                        reverseFlag ? tree[s2].push_back(s1) : tree[s1].push_back(s2); // 构建树 并始终保持方向从beginWord指向endWord
                    }
                }
            }
            bfsFromBegin = next; // 更新队列
            if (bfsFromBegin.size() > bfsFromEnd.size())
            {
                reverseFlag = !reverseFlag;     // 取反
                swap(bfsFromBegin, bfsFromEnd); // 交换BFS的队列 改变BFS的方向
            }
            if (findFlag)
                break; // 双向BFS交汇 BFS过程终止
        }
        vector<string> cur = {beginWord};
        dfs(cur, beginWord, endWord); // 遍历形成的树 得到起点到终点的路径
        return ans;
    }
};