词语序列ii

从hit到cog之间有许多路径，我们可以将其想像成一个图：

两种方法：

• BFS记录每个单词所在层再DFS，176ms, 2924KB
• 构建图再回溯，156ms, 4580KB

方法一：BFS记录图中单词所在层再DFS

先通过BFS记录图里面单词所在的层，然后通过DFS找到所有的路径：

1. BFS过程中需要记录历史节点及当前层次，最终获取每一个单词对应的层级
2. DFS的终止条件是搜索到了结束单词

//
// Created by jt on 2020/9/23.
//
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution {
public:
    vector<vector<string>> findLadders(string start, string end, vector <string> &dict) {
        vector<vector<string>> res;
        // 建立单词与其相邻单词的map
        unordered_set<string> uset(dict.begin(), dict.end());
        if (uset.count(end) == 0) return res;
        uset.insert(start); uset.insert(end);
        unordered_map<string, vector<string>> wordMap;
        for (auto it = uset.begin(); it != uset.end(); ++it) {
            for (int i = 0; i < it->size(); ++i) {
                for (int c = 'a'; c <= 'z'; ++c) {
                    if (it->data()[i] == c) continue;
                    string str = it->data(); str[i] = c;
                    if (uset.count(str) != 0) {
                        wordMap[it->data()].push_back(str);
                    }
                }
            }
        }
        // 广度优先遍历记录每个单词所在层
        unordered_map<string, int> visitedLevel;
        queue<string> qu;
        qu.push(start);
        int level = 1, quSize = 1;      // level既是当前层级，也是[最短路径长度-1]
        visitedLevel[start] = 1;
        while (!qu.empty()) {
            if (visitedLevel.count(end) && visitedLevel[end] <= level) break;
            string str = qu.front(); qu.pop();
            for (auto &a : wordMap[str]) {
                if (visitedLevel.count(a) == 0) {
                    visitedLevel[a] = level + 1;
                    qu.push(a);
                }
            }
            if (--quSize == 0) { level++; quSize = qu.size(); }
        }
        // 深度优先遍历查找所有最短路径
        vector<string> vec = {start};
        dfs(res, visitedLevel, wordMap, vec, end);
        return res;
    }

    void dfs(vector<vector<string>> &res, unordered_map<string, int> &visitedLevel,
             unordered_map<string, vector<string>> &wordMap,
             vector<string> &vec, string target) {
        if (vec[vec.size()-1] == target) { res.push_back(vec); return; }
        string word = vec[vec.size()-1];
        for (auto &str : wordMap[word]) {
            if (visitedLevel.count(str) && visitedLevel[str] == vec.size()+1) {
                vec.push_back(str);
                dfs(res, visitedLevel, wordMap, vec, target);
                vec.pop_back();
            }
        }
    }
};

方法二：构建图再回溯

整体方案：

• 从hit开始构造这个图
• 然后从cog出发，反向查找出所有的最短路径

构造图的思路：

1. 首先，可以获取每个单词变更一个字母后在输入字典中的所有对应单词，如dot对应lot/hot/dog
2. 利用BFS从起始节点开始填充它的下一层节点，如果某个单词已经在本层或者上面的层出现过，那么忽略之
3. 如果出现了终止单词，记录终止节点的位置

注：举例说明第2点，如果当前节点的单词为dot，对应的下一层节点的单词为lot/hot/dog，但是其中lot与dot在同一层，甚至更高层，则可以忽略lot

反向回溯的思路：

• 从终止节点出发进行回溯（DFS），如果找到了起始单词，将当前路径加入结果
• 输出最短路径对应的结果

代码如下：

//
// Created by jt on 2020/9/23.
//
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

// 存储图的节点
struct GraphNode{
    string word;
    vector<GraphNode*> parents;
    vector<GraphNode*> sons;
    GraphNode(string w): word(w) {}
};

class Solution {
public:
    vector<vector<string>> findLadders(string start, string end, vector <string> &dict) {
        vector<vector<string>> res;
        // 构建每个单词与其他单词的转换关系
        if (dict.empty() || start.size() < 1 || end.size() < 1) return res;
        unordered_set<string> unorderedSet(dict.begin(), dict.end());
        unorderedSet.insert(start);
        unorderedSet.insert(end);
        unordered_map<string, vector<string>> wordMap;
        for (auto it = unorderedSet.begin(); it != unorderedSet.end(); ++it) {
            for (int i = 0; i < it->size(); ++i) {
                for (char a = 'a'; a <= 'z'; ++a) {
                    if (a == it->data()[i]) continue;
                    string str = it->data();
                    str[i] = a;
                    if (unorderedSet.count(str) != 0) {
                        if (wordMap.count(it->data())) wordMap[it->data()].push_back(str);
                        else wordMap[it->data()] = {str};
                    }
                }
            }
        }
        // 构建图
        unordered_map<string, GraphNode*> visitedPointer;  // 记录已经出现过的单词，以及对应的指针
        unordered_map<string, int> visitedLevel;           // 记录已经出现过的单词，以及对应的层级
        queue<GraphNode*> qu;
        GraphNode *head = new GraphNode(start), *tail = nullptr;
        visitedPointer[start] = head;
        visitedLevel[start] = 0;
        qu.push(head);
        int level = 0, cnt = 1;         // 记录当前层的ID以及节点个数
        while (!qu.empty()) {
            GraphNode *p = qu.front();
            qu.pop();
            for (auto str : wordMap[p->word]) {
                GraphNode *node;
                if (visitedPointer.count(str) != 0) {
                    // 如果单词出现在本层甚至更高层级，略过
                    if (visitedLevel[str] <= level) continue;
                    else node = visitedPointer[str];
                } else {
                    node = new GraphNode(str);
                    if (str == end) tail = node;            // 如果是终止单词，记录尾部节点
                    visitedPointer[str] = node;
                    visitedLevel[str] = level + 1;
                    qu.push(node);
                }
                node->parents.push_back(p);
                p->sons.push_back(node);
            }
            // 更新层ID
            if (--cnt == 0) { level++; cnt = qu.size(); }
        }
        // 反向回溯图
        vector<string> vec = {end};                  // 存储路径
        dfs(tail, vec, res);
        return res;
    }

    void dfs(GraphNode *node, vector<string> &vec, vector<vector<string>> &res) {
        if (!node) return;
        if (node->parents.empty()) {
            reverse(vec.begin(), vec.end());
            res.push_back(vec);
            reverse(vec.begin(), vec.end());
            return;
        }
        for (auto p : node->parents) {
            vec.push_back(p->word);
            dfs(p, vec, res);
            vec.pop_back();
        }
    }
};