题目：
链接：https://leetcode-cn.com/problems/word-ladder-ii/
给定两个单词（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" 不在字典中，所以不存在符合要求的转换序列。
解答：
1.首先抽象成图，那么要求的转换序列长度就是beginWord到endWord的最短路径的边数，相邻节点改变一位就互相可达，如：hot和hog，cat和cot等等。所以先建图肯定免不了，我们果断先建立邻接表再说。
2.然后考虑求所有路径，那一般来说肯定得用dfs了。但是直接dfs可能有如下情况：实际最短路径可能就两步，即beginWord---->某单词---->endWord。但给了几百个节点，我们dfs遍历的绝大部分都是无用的，所以考虑需要剪枝处理。
3.接下来想到了先用bfs确定最短路径的长度，再用dfs查找所有的最短路径。但无奈剪枝不够，第31个用例吧好像，最短路径长度是19，基本相当于没剪枝，所以就一直AC不了。
后来看了下面链接的题解，用了一个特别的方法来剪枝：即之前bfs查找最短路径的长度时，用一个哈希表存储每个单词第一次出现的长度，比如有beginWord--->a->b->c，还有beginWord--->c，那么我们从beginWord开始dfs的时候，取其相邻节点时，要检查之前的哈希表，看当前单词是不是第一次出现的位置，如果不是，就没必要考察了，因为肯定不是最短路径。（建议还是去看下面链接，很清楚）
大神题解链接，回头温习，写的真是太牛了：
https://leetcode-cn.com/problems/word-ladder-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-3-3/
代码如下，还是蛮多行的：
1 class Solution {
2 public:
3 vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
4 if(find(wordList.begin(),wordList.end(),endWord)==wordList.end()){return {};}
5 wordList.emplace_back(beginWord);
6 unordered_map<string,vector<string>> dic;
7 for(string& wd:wordList){
8 string s=wd;
9 for(int i=0;i<s.size();++i){
10 s[i]='#';
11 dic[s].emplace_back(wd);//eg: "hot":分为"#ot","h#t","ho#"
12 s=wd;
13 }
14 }
15 unordered_map<string,unordered_set<string>> graph;//邻接表
16 for(string& wd:wordList){
17 string s=wd;
18 for(int i=0;i<s.size();++i){
19 s[i]='#';
20 for(const string& neighbour:dic[s]){
21 graph[wd].insert(neighbour);
22 }
23 s=wd;
24 }
25 graph[wd].erase(wd);//删除自己
26 }
27 //从endWord开始找，先用BFS找一个最短转换的长度
28 queue<string> que;
29 que.push(endWord);
30 unordered_map<string,int> first_show;//每个单词第一次出现的层数（从endWord倒着算起）
31 unordered_set<string> visited={endWord};//考察过的记录在里面
32 int min_len=0,step=0;
33 string cur;
34 while(not que.empty()){
35 int cur_len=que.size();
36 for(int i=0;i<cur_len;++i){
37 cur=que.front();
38 que.pop();
39 if(first_show.count(cur)==0){
40 first_show[cur]=step;
41 }
42 if(cur==beginWord){//找到起始单词则退出循环
43 min_len=step;
44 break;
45 }
46 for(const string& neighbour:graph[cur]){
47 if(visited.count(neighbour)==0){//一步能到达的邻居，如果没遍历过则放到队尾
48 que.push(neighbour);
49 visited.insert(neighbour);
50 }
51 }
52 }
53 if(cur==beginWord){break;}
54 ++step;
55 }
56 if(min_len==0){return {};}
57 //用DFS找所有长度为min_len的解
58 vector<string> temp={endWord};
59 vector<vector<string>> res;
60 visited.clear();
61 dfs(res,first_show,temp,beginWord,0,min_len,visited,graph);
62 for(auto& vec:res){
63 reverse(vec.begin(),vec.end());
64 }
65 return res;
66 }
67 void dfs(vector<vector<string>>& res,unordered_map<string,int>& first_show,vector<string>&cur,string target,int cur_len,int target_len,unordered_set<string>& visited,unordered_map<string,unordered_set<string>>& graph){
68 if(cur_len>=target_len){
69 if(cur.back()==target){
70 res.emplace_back(cur);
71 }
72 return;
73 }
74 for(const string& nei:graph[cur.back()]){
75 if(visited.count(nei)==0 and first_show[nei]==cur_len+1){
76 cur.emplace_back(nei);
77 visited.insert(nei);
78 dfs(res,first_show,cur,target,cur_len+1,target_len,visited,graph);
79 cur.pop_back();
80 visited.erase(nei);
81 }
82 }
83 }
84 };
