题目：

题解：

本题是上一题127.单词接龙的变形，首先我们利用bfs（bfs的特性：源节点到任何节点的path都是最短路径）进行遍历找出最短路径，我们将已访问过的单词存放在集合del中，不要立即删除。因为在同一层遍历中，可能存在多条路径，也就是多个解，这也是与127区别所在。我们使用trace来记住当前单词和当前单词的前驱，例如：cog的前驱有dog和log两个，然后我们使用dfs来遍历trace便可将所有路径还原。

代码如下：

class Solution {
private:
 void dfs(unordered_map<string, unordered_set<string> >& trace, const string& last, vector<string> path, vector<vector<string> >& vs) {
  path.push_back(last);
  if (trace.count(last) == 0) {//当last不存在于trace时，表示一条路径已走完了，添加到结果中即可
   reverse(path.begin(), path.end());
   vs.push_back(path);
   return;
  }
  for (const string& word : trace[last])//由于trace中当前单词的前缀有多个，比如cog的前缀有dog和log,所以遍历trace便可将所有路径还原
   dfs(trace, word, path, vs);
 }
 
public:
 //题解：bfs+dfs
 vector<vector<string>> findLadders(string begin, string end, vector<string>& wordList) {
  //1:建立词典表，顺便去掉重复元素
  unordered_set<string> dic(wordList.begin(), wordList.end());
  
  //2:极端情况，end不在词典中
  if (dic.count(end) == 0)return {};

  //3:bfs的初始化工作
  unordered_map<string, unordered_set<string>> trace;//路径，存在<当前单词，当前单词的前缀>，目标单词的前缀有多个，代表多个解
  unordered_set<string> q{ begin }, del;
  
  //4:进行bfs
  while (q.size() && trace.count(end) == 0)//当目标单词添加到路径时，循环结束
  {
   for (const auto& word : q)dic.erase(word);//删除词典中已存在于q的单词
   del.clear();//清空待删除单词的词典
   for (const auto& word : q) {
    for (int i = 0; i < word.size(); ++i) {
     string s = word;
     for (char ch = 'a'; ch <= 'z'; ++ch) {
      if (word[i] == ch)continue;//跳出此次循环，继续寻找某个字符不一样的单词
      s[i] = ch;
      if (dic.count(s) == 0)continue;//词典中不存在该单词s,跳出此次循环，寻找下一个存在的单词
      trace[s].insert(word);
      del.insert(s);
      }
    }
   }
   q = del;
  }
  
  if (trace.size() == 0)return {};
  vector<vector<string>> result;
  dfs(trace, end, {}, result);//利用dfs恢复路径
  return result;
 }
};