力扣打卡，单词接龙Ⅱ（构图|力扣打卡，单词接龙Ⅱ（构图 + BFS + DFS) 力扣打卡，单词接龙Ⅱ（构图

【力扣打卡，单词接龙Ⅱ（构图|力扣打卡，单词接龙Ⅱ（构图 + BFS + DFS)】原题连接
思路：首先建图，建一个无向图；将字典里的每一个单词看作一个点，如果两个单词只差一个字母，那么就将这两个节点之间加一条边；
使用广度优先搜索，再遍历过程中同时记录可达节点的父节点，便于之后回溯枚举所有的答案。
当活结点进行扩展时，要满足一个条件才能成为父节点：当前距离 + 1 <= 扩展的结点的已有距离（距离是指：扩展的层数）
扩展结点加入队列，要满足二个条件：其一，需要满足上面的条件。其二，这个结点之前没有被访问过；
//bfs: 确定最短路径；找到所有最短路径（永远只压入“当前距离 + 1 <= 扩展的结点的已有距离，没有被访问过”的结点；通过记录父节点，可以回溯找到所有最短路径）

//建无向链接图时，只需遍历一半的元素；因为无向图i -> j==j -> i; // 1 -> 2 、 2 -> 1 /* for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) */ for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int t = 0; for (int k = 0; k < wordList[i].size(); k++) { if (wordList[i][k] != wordList[j][k]) { t++; if (t > 1) { t = -1; break; } } } if (t != -1) { vv[i].push_back(j); vv[j].push_back(i); } } }

实现代码：

class Solution { public: vector> vvs; vector> vs; vector> words; vector> ff; vector father; void dfs(int pos) { if (pos == words.size() - 1) { //vs.push_back(wordList[si]); vvs.push_back(vs); //vs.pop_back(); return; }for (int i = 0; i < ff[pos].size(); i++) { vs.push_back(words[ff[pos][i]]); dfs(ff[pos][i]); vs.pop_back(); } return; } vector> findLadders(string beginWord, string endWord, vector>& wordList) { int i = 0,ei; for (; i < wordList.size(); i++) { if (endWord == wordList[i]) { ei = i; break; } } if (i == wordList.size()) return {}; wordList.push_back(beginWord); vector> vv(wordList.size(), vector()); vector dist(wordList.size(),0x3f3f3f3f); vector> father(wordList.size(), vector()); vector vist(wordList.size(), 0); queue q[2]; int top,a = 0, b = 1,n; n = wordList.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (i == j) continue; int t = 0; for (int k = 0; k < wordList[i].size(); k++) { if (wordList[i][k] != wordList[j][k]) { t++; if (t > 1) { t = -1; break; } } } if (t != -1) { vv[i].push_back(j); vv[j].push_back(i); } } } q[a].push(n - 1); dist[n - 1] = 0; vist[n - 1] = true; while (!q[a].empty()) { while (!q[a].empty()) { top = q[a].front(); q[a].pop(); //if (top == ei) // continue; for (int i = 0; i < vv[top].size(); i++) { if (dist[top] + 1 <= dist[vv[top][i]]) { father[vv[top][i]].push_back(top); dist[vv[top][i]] = dist[top] + 1; if (!vist[vv[top][i]]) { vist[vv[top][i]] = true; q[b].push(vv[top][i]); } } } } if (vist[ei]) break; swap(a, b); } if (!vist[ei]) return {}; ff = father; words = wordList; vs.push_back(endWord); dfs(ei); for (int i = 0; i < vvs.size(); i++) { reverse(vvs[i].begin(), vvs[i].end()); //颠倒顺序 } return vvs; } };

//bfs