126. Word Ladder II

bfs + dfs O(nm) n是单词个数 m是单词平均长度
这道题的本质是求单源最短路径，应该使用dijkstra算法，这样可以只记录到每个点最短的那些路径，避免把较长的路径也记录下来
dijkstra把从beginWord到其他词（包括endWord）的所有最短路径都找出来（用邻接表）
再用dfs把到endWord的所有最短路径打印出来

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, int> d; // 记录源点到每个点的最短距离
        for (const auto &u : wordList) {
            d[u] = INT_MAX; // 初始化源点到每个点的距离都是无穷大
        }

        unordered_map<string, vector<string>> next;
        queue<string> q; // dijkstra算法本来应该使用优先队列，但是这道题里每次入队列的单词到beginWord的转换步数都是大于等于队列内的其他单词的，所以普通队列即可
        q.push(beginWord);
        d[beginWord] = 0; // 初始化源点到其自己的距离为0
        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            if (u == endWord) break; // 因为只要步数一样就写入图里，所以相当于按层遍历的，最短的可以达到endWord这一层的所有边都已经写到图里了，所以当查看下一层的时候第一次找到endWord就可以跳出循环了
            auto v = u;
            for (auto &&c : v) { // relax
                auto t = c;
                for (char x = 'a'; x <= 'z'; ++x) {
                    c = x;
                    if (x == t || d.count(v) == 0 || d[v] < d[u] + 1) continue; // d[v] < d[u] + 1的意思是v已经访问过了且源点到v的距离应该小于等于源点到u的距离，即v在之前已经可以用更少的转换步数得到，则现在通过u转换得到v的步数不是更少的
                    if (d[v] > d[u] + 1) {
                        d[v] = d[u] + 1;
                        q.push(v);
                    }
                    next[u].push_back(v); // 这里只要u->v不会让到v的最短距离变长就记录下来（因为要找『所有』最短距离，即使d[v] == d[u] + 1也要记录下来），另外因为bfs导致永远是较近的点先被放入，所以一定不会出现先加入『长边』再加入『短边』的情况
                }
                c = t;
            }
        }

        vector<string> v;
        vector<vector<string>> res;
        v.push_back(beginWord);
        dfs(beginWord, endWord, next, v, res);
        return res;
    }

    void dfs(const string &w, const string &e, unordered_map<string, vector<string>> &next, vector<string> &v, vector<vector<string>> &res) {
        if (w == e) {
            res.push_back(v);
            return;
        }
        for (const auto &n : next[w]) {
            v.push_back(n);
            dfs(n, e, next, v, res);
            v.pop_back();
        }
    }
};

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, int> d;
        for (const auto &w : wordList) {
            d[w] = INT_MAX;
        }
        queue<string> q;
        q.push(beginWord);
        d[beginWord] = 0;
        while (!q.empty()) {
            auto u = q.front(); q.pop();
            if (u == endWord) break;
            auto v = u;
            for (char &c : v) {
                char t = c;
                for (char x = 'a'; x <= 'z'; ++x) {
                    c = x;
                    if (x == t || !d.count(v) || d[v] < d[u] + 1) continue;
                    if (d[v] > d[u] + 1) {
                        d[v] = d[u] + 1;
                        q.push(v);
                    }
                    next[u].push_back(v);
                }
                c = t;
            }
        }
        vs.push_back(beginWord);
        dfs(beginWord, endWord);
        return res;
    }

    void dfs(const string &b, const string &e) {
        if (b == e) {
            res.push_back(vs);
            return;
        }
        for (const auto &n : next[b]) {
            vs.push_back(n);
            dfs(n, e);
            vs.pop_back();
        }
    }

    unordered_map<string, vector<string>> next;
    vector<string> vs;
    vector<vector<string>> res;
};