给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母。 转换后得到的单词必须是字典中的单词。 说明:
如果不存在这样的转换序列，返回一个空列表。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。 示例 1:
输入: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出: [ [“hit”,“hot”,“dot”,“dog”,“cog”], [“hit”,“hot”,“lot”,“log”,“cog”] ] 示例 2:
输入: beginWord = “hit” endWord = “cog” wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出: []
解释: endWord “cog” 不在字典中，所以不存在符合要求的转换序列。 通过次数20,178提交次数52,654
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/word-ladder-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路： 和之前的单词接龙的整体思想一致，都是通过构建图，之后通过bfs算法找到最短路径。不同的地方在于，需要思考出保存路径的解决办法，同时要找出所有不同的，但都是最短长度的路径。解决办法是，在广度优先搜索队列中，保存当前节点的遍历路径，而并不是单单保存当前的节点。同时，visit数组也要做相应的更改，保存遍历到该节点的最短的路径长度，这个样可以根据visit数组来每次进行判断当前是否被遍历过，或者说，更新每个节点使用最小花销的路径。实现细节，在代码中有注释。 ps：发现在进行一步之前，思考好整个流程，记下注释是个好习惯，能够使得之后的编码不会中断。
/* 思路：利用map构建字符串到int类型id的映射，利用vector<string>构建反向的映射； 这样就可以使用二维vector来进行图的构建 */ class Solution { public: vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { //完成相互映射 unordered_map<string,int> word2Id; vector<string> id2Word; int id = 0; for(auto str:wordList) { word2Id[str] = id++; id2Word.push_back(str); } //检查beginword是否在内； if(!word2Id.count(beginWord)) { word2Id[beginWord] = id++; id2Word.push_back(beginWord); } //检查endword是否在内 if(!word2Id.count(endWord)) return {}; //构建图 vector<vector<int>> graph; graph.resize(id2Word.size()); for(int i = 0;i<id2Word.size();i++) { for(int j = i+1;j<id2Word.size();j++) { //cout<<j<<endl; //cout<<id2Word.size()<<endl; if(isConnect(id2Word[i],id2Word[j])) { graph[i].push_back(j); graph[j].push_back(i); } } } //初始化所需要的数据结构 vector<vector<string>> ret; queue<vector<int>> q; vector<int> visit(word2Id.size(),1<<20); q.push(vector<int>{word2Id[beginWord]}); visit[word2Id[beginWord]] = 0; int target = word2Id[endWord]; while(!q.empty()) { vector<int> cur = q.front(); q.pop(); int node = cur.back(); if(node == target) { vector<string> temp; for(auto index:cur) { temp.push_back(id2Word[index]); } ret.push_back(temp); } else { for(int i = 0;i<graph[node].size();i++) { //排除掉能够以更短路径访问到该节点 if(visit[graph[node][i]]>=visit[node]+1) { visit[graph[node][i]] = visit[node]+1; vector<int> temp = cur; temp.push_back(graph[node][i]); q.push(temp); } } } } return ret; } bool isConnect(const string& a,const string& b) { int count = 0; for(int i =0;i<a.size()&&count<2;i++) { if(a[i]!=b[i])count++; } return count==1; } };