126-单词接龙

LeetCode 127. 单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

method: 双向BFS

哈希表存出现过的单词的level，扩展的时候，如果在哈希表中，说明已经扩展过了，就不用管，否则，更新扩展单词的level，并加入到队列中

结果是路径上的节点数，是tmp在两边的level相加再加1，所以是cur[tmp] + other[tmp] + 1

unordered_set<string> st;
unordered_map<string, int> mp1, mp2;
queue<string> q1, q2;
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    for (auto s : wordList) {
        st.insert(s);
    }
    if (st.count(endWord) == 0) return 0;
    q1.push(beginWord);
    mp1[beginWord] = 0;
    q2.push(endWord);
    mp2[endWord] = 0;
    int res = bfs();
    return res == -1 ? 0 : res + 1;
}
int bfs() {
    while (!q1.empty() && !q2.empty()) {
        int res = -1;
        if (q1.size() <= q2.size()) {
            res = update(q1, mp1, mp2);
        } else {
            res = update(q2, mp2, mp1);
        }
        if (res != -1) return res;
    }
    return -1;
}
int update(queue<string>& q, unordered_map<string, int>& cur, unordered_map<string, int>& other) {
    int size = q.size();
    while (size--) {
        string str = q.front();
        q.pop();
        for (int i = 0; i < str.size(); i++) {
            string tmp = str;
            for (char j = 'a'; j <= 'z'; j++) {
                tmp[i] = j;
                if (st.count(tmp)) {    // 存在集合中才有效
                    if (cur.count(tmp)) continue;   // 出现过就不管了
                    if (other.count(tmp)) { // 出现在另一个哈希表中就说明找到了最短路劲
                        return cur[str] + 1 + other[tmp];
                    }
                    cur[tmp] = cur[str] + 1;
                    q.push(tmp);
                }
            }
        }
    }
    return -1;
}

---

126. 单词接龙 II

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：

• 每对相邻的单词之间仅有单个字母不同。
• 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
• sk == endWord

给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

method: 双向BFS+反向DFS

构建无向图

str1和str2都要处理，因为可能找到的路径是一样长的，所以都需要构建边

如果tmp已经出现过，被赋予了level，但是刚好是当前str的level+1，这样也可以构建边，例如这里的str2->tmp1，不过这样也说明tmp1已经在队列中了，就不用在入队了

反向DFS：从endWord开始往前找，直到找到beginWord，主要是因为有特殊数据，正向会超时

unordered_set<string> st;
queue<string> q1, q2;
unordered_map<string, vector<string>> map;
unordered_map<string, int> mp1, mp2;
vector<string> path;
vector<vector<string>> res;
bool update(queue<string>& q, unordered_map<string, int>& cur, unordered_map<string, int>& other, bool isForward) {
    bool isFound = false;
    int size = q.size();
    while (size--) {
        auto str = q.front();
        q.pop();
        for (int i = 0; i < str.size(); i++) {
            string tmp = str;
            for (char j = 'a'; j <= 'z'; j++) {
                tmp[i] = j;
                if (st.count(tmp)) {
                    if (cur.count(tmp) == 0 || cur[tmp] == cur[str] + 1) {	// 没出现过，或者刚好在下一层
                        if (isForward) map[tmp].push_back(str);	// 可以建立边，注意是反向建图
                        else map[str].push_back(tmp);
                    }
                    if (cur.count(tmp) == 0) {	// 如果没出现过就赋予level，并加入队列
                        cur[tmp] = cur[str] + 1;
                        q.push(tmp);
                    }
                    if (other.count(tmp)) {	// 出现在另一边的哈希表中，说明找到了一条路径
                        isFound = true;	// 这一层要全部处理完，所以不能在这里return
                    }
                }
            }
        }
    }
    return isFound;
}
bool bfs() {
    while (!q1.empty() && !q2.empty()) {
        bool res = false;
        if (q1.size() <= q2.size()) {
            res = update(q1, mp1, mp2, true);
        } else {
            res = update(q2, mp2, mp1, false);
        }
        if (res) return res;
    }
    return false;
}
void dfs(string& s, string& target) {
    if (s == target) {
        res.push_back({path.rbegin(), path.rend()});	// 这里要反转一下
        return;
    }
    for (auto ns : map[s]) {
        path.push_back(ns);
        dfs(ns, target);
        path.pop_back();
    }
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
    for (auto s : wordList) st.insert(s);
    if (st.find(endWord) == st.end()) return res;
    q1.push(beginWord);
    mp1[beginWord] = 0;
    q2.push(endWord);
    mp2[endWord] = 0;
    int ans = bfs();    // 双向BFS
    if (!ans) return res;
    path.push_back(endWord);	// 反向DFS
    dfs(endWord, beginWord);
    return res;
}