【题目】

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:

start = "hit"

end = "cog"

dict = ["hot","dot","dog","lot","log"]

Return

[    ["hit","hot","dot","dog","cog"],    ["hit","hot","lot","log","cog"]  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

【题意】

    给定两个单词start和end, 一个词典，找到全部的最短转换序列。

几个注意事项：

    1. 每次变换仅仅能改变一个字符

    2. 变换的中间单词必须在词典中

    3. 全部单词长度同样

    4. 全部单词字符都小写

【思路】

     思路和word Ladder是同样的，仅仅只是本题须要把左右的序列输出。

     为了恢复转换序列在搜索的过程中，我们须要记录每一个可达单词的前继单词（所谓单词可达，就是start通过若干次字符变换后能够转换成当前单词）。

     一旦我们找到end, 我们就能够通过前继恢复路径。这跟用dijkstra找最短路径的方法事实上非常相似。

    

【代码】

class Solution {public:    void getSequences(vector
       
        
          >&result, vector
         
          &sequence, string&start, string end, map
          
            >&percursors){        sequence.push_back(end);        if(start==end){            vector
           
             v=sequence;            reverse(v.begin(), v.end());            result.push_back(v);            return;        }                //找end的前驱        vector
            
              pres = percursors[end]; for(int i=0; i
             
               > findLadders(string start, string end, unordered_set
              
                &dict) { vector
               
                
                  > result; if(start==end)return result; //记录前驱的map map
                 
                   > percursors; //标记是否已经找到最短序列 bool isFind=false; //交替存储相邻 queue
                  
                    q1; queue
                   
                     q2; q1.push(start); //找前驱 while(!q1.empty() || !q2.empty()){ //存放当前层单词 set
                    
                      words; if(!q1.empty()){ while(!q1.empty()){ string curword=q1.front(); q1.pop(); for(int i=0; i
                     
                      ::iterator it=words.begin(); it!=words.end(); it++){ q2.push(*it); dict.erase(*it); } } else{ while(!q2.empty()){ string curword=q2.front(); q2.pop(); for(int i=0; i
                      
                       ::iterator it=words.begin(); it!=words.end(); it++){ q1.push(*it); dict.erase(*it); } } if(isFind)break; } //生成全部序列 vector
                       
                        sequence; getSequences(result, sequence, start, end, percursors); return result; }};