给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母。转换过程中的中间单词必须是字典中的单词。说明:
如果不存在这样的转换序列，返回一个空列表。所有单词具有相同的长度。所有单词只由小写字母组成。字典中不存在重复的单词。你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
思路：
这个题目与127很相似，但是127只需要求出最短路径长，因此只采用BFS就可以满足要求。
现在要求求出所有最短路径，如果还沿用BFS是找不出所有路径的，因此考虑用DFS。
但使用DFS，如果图比较复杂，会发现出现超时。
因此考虑对图进行精简，不能完全构图。
因此考虑讲图进行分层，每一层的某个节点与下一层的所有节点只有某个位置的字母不同，这样实际上图简单不少，与上层的关系接近于有向图，防止遍历到本层时又向上层遍历；在本层间没有连通。
这样构图后，最后一层一定是endWord所在的那一层，因此只要出现某一层出现了endWord，就停止构图。
在这样的图中进行DFS，只要找到了endWord就一定是最短路径那一条，因为每次遍历都是在向下一层遍历，而层数是固定的。
代码值得注意的两个地方：
1.构图：
用一个unordered_map<string,unordered_set<string>>的数据结构表示图，string为当前节点，undered_set<string>为与这个节点相邻的下一层集合。
cur表示当前层，next表示下一层，遍历cur的每个节点，构建好图：graph[*it].insert(tmp)，并在下一层中加入:next.insert(tmp)。
另外为了防止遍历到本层时又回到上一层，因此next构建完毕后要讲next层中的节点在字典dict中删去。
最后直到cur层中有endWord才停止，或dict已查找完毕才停止。
2.DFS遍历：
没什么好特别强调的，从beginWord出发，一层一层的遍历节点，直到endWord，将路径加入到result。
class Solution { public: vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { unordered_map<string,unordered_set<string>> graph; unordered_set<string> cur; unordered_set<string> next; unordered_set<string> dict; for(int i=0;i<wordList.size();i++) dict.insert(wordList[i]); cur.insert(beginWord); if(dict.count(beginWord)>0) dict.erase(beginWord); while(cur.count(endWord)==0&&dict.size()!=0) { for(auto it=cur.begin();it!=cur.end();it++) { string tmp=*it; for(int i=0;i<tmp.size();i++) { for(int k=0;k<26;k++) { tmp[i]=(char)('a'+k); if(dict.find(tmp)!=dict.end()) { graph[*it].insert(tmp); next.insert(tmp); } } tmp=*it; } } if(next.size()==0) break; for(auto it=next.begin();it!=next.end();it++) { dict.erase(*it); } cur=next; next.clear(); } vector<vector<string>> result; if(cur.count(endWord)==0) return result; vector<string> input; dfs(result,input,beginWord,endWord,graph); return result; } private: void dfs(vector<vector<string>> &result,vector<string> input,string start,string end,unordered_map<string,unordered_set<string>>& graph) { if(start==end) { input.push_back(start); result.push_back(input); return; } input.push_back(start); for(auto it=graph[start].begin();it!=graph[start].end();it++) { dfs(result,input,*it,end,graph); } return ; } };
转载于:https://www.cnblogs.com/lxy-xf/p/11176076.html
