给定两个单词（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 ;
}
};