leetcode: Word Ladder II

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"]
     ]

   
   

   本題5星難度，和I一樣用bfs，但是因為要輸出，所以時間不夠

   先遍歷找到每個詞的前驅詞，用兩個隊列保存當前層和之前層的詞，一個是正在處理，一個是下次需要處理

   得到前驅詞表後，從end往前遞歸打印路徑

   AC代碼

   class Solution {
   public:
       vector< vector< string> > res;
       vector> findLadders(string start, string end, unordered_set &dict) {
           dict.insert(start);
           dict.insert(end);
           unordered_map< string, vector< string> > precursor;//保存每個詞對應的前驅詞
           for( unordered_set< string>::const_iterator citer = dict.begin(); citer != dict.end(); ++citer)//初始化
               precursor.insert( make_pair( *citer, vector< string>()));
           vector< unordered_set< string> >layers(2);//分別用來保存當前層的詞和之前層的詞
           layers[0].insert(start);
           int cur = 0;
           int pre = 1;
           while(true){
               cur = !cur;//兩層互換
               pre = !pre;
               for( unordered_set< string>::const_iterator citer = layers[pre].begin(); citer != layers[pre].end(); ++citer)
                   dict.erase(*citer);//刪除之前層裡出現在字典裡的詞
               layers[cur].clear();
               //bfs搜索之前層裡每個詞通過一次變換可以達到的詞，該詞如果在字典裡就放入當前層
               for( unordered_set< string>::const_iterator citer = layers[pre].begin(); citer != layers[pre].end(); ++citer){
                   string str = *citer;
                   for( int i = 0; i < str.size(); ++i){
                       for( int j = 'a'; j <= 'z'; ++j){
                           if( str[i] == j)
                               continue;
                           string tmp = str;
                           tmp[i] = j;
                           if( dict.count(tmp)){
                               precursor[tmp].push_back(str);
                               layers[cur].insert(tmp);
                           }
                       }
                   }
               }
               if( layers[cur].empty())//如果當前層空，說明無法從start到end，結束
                   return res;
               if( layers[cur].count(end))//如果當前層出現end，說明已經找到了轉換，而且因為是根據層數來的，所以都是shortest
                   break;
           }
           vector< string> path;
           generatePath( precursor, path, end);
           return res;
       }
       //從end開始從後往前遞歸
       void generatePath( unordered_map< string, vector< string> > &precursor, vector< string> &path, string end){
           if( precursor[end].size() == 0){//沒有前驅詞說明已經到了start
               path.push_back(end);
               vector< string> tmp = path;
               reverse( tmp.begin(), tmp.end());//反轉次序
               res.push_back(tmp);
               path.pop_back();
           }
           path.push_back(end);
           for( vector< string>::const_iterator citer = precursor[end].begin(); citer != precursor[end].end(); ++citer){
               generatePath( precursor, path, *citer);
           }
           path.pop_back();
       }
   };

   
   
   

   TLE得一塌糊塗，還是不能用遞歸的

   class Solution {
   public:
       
       vector> findLadders(string start, string end, unordered_set &dict) {
           vector< vector< string> > res;
           vector< string> cur;
           cur.push_back(start);
           dict.insert(end);
           unordered_set< string> tmp = dict;
           int length = ladderLength(start, end, tmp);
           core( res, cur, start, end, dict, length);
           return res;
       }
       void core( vector< vector< string> > &res, vector< string> &cur, string start, string end, unordered_set< string> &dict, int l){
           if( cur.size() > l)
               return;
           if( start == end){
               res.push_back(cur);
               return;
           }
           for( int i = 0; i < start.size(); ++i){
               for( int j = 'a'; j <= 'z'; ++j){
                   if( start[i] == j)
                       continue;
                   else{
                       string tmp = start;
                       tmp[i] = j;
                       if( dict.count(tmp)){
                           cur.push_back(tmp);
                           dict.erase(tmp);
                           core( res, cur, tmp, end, dict, l);
                           cur.pop_back();
                           dict.insert(tmp);
                       }
                   }
               }
           }
       }
       int ladderLength(string start, string end, unordered_set &dict) {
           int shortest = INT_MAX;
           dict.insert(end);
           queue< pair< string, int> > q;
           q.push( pair< string, int>( start, 1));
           while( !q.empty()){
               pair< string, int> cur = q.front();
               q.pop();
               if( cur.first == end){
                   shortest = shortest < cur.second ? shortest : cur.second;
                   continue;
               }
               string str = cur.first;
               for( int i = 0; i < str.size(); ++i){
                   for( int j = 'a'; j <= 'z'; ++j){
                       if( str[i] == j)
                           continue;
                       string tmp = str;
                       tmp[i] = j;
                       if( dict.count(tmp)){
                           q.push( make_pair( tmp, cur.second+1));
                           dict.erase(tmp);
                       }
                   }
               }
           }
           if( shortest == INT_MAX)
               return 0;
           return shortest;
       }
   };