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

Note:

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

The solution is quite long and can be divided to several parts:


class Solution {
public:
void calAdj(const string s, unordered_set<string> & dict, unordered_set<string>& adjset){
     adjset.clear();
     for( int i = 0; i < s.size(); i++){
         string tmp(s);
         for( char az = 'a'; az <= 'z'; az++){
             tmp[i] = az;
             if( dict.find(tmp) != dict.end()){ //tmp is in dictionary
                 adjset.insert(tmp);
             }
         }
     }
}
void pathreverse(unordered_map<string, unordered_set<string>>& pathmap, string start, vector<vector<string>>& pathlist){
     vector<string> & lastpath = pathlist[pathlist.size()-1];
     lastpath.push_back( start );
     vector<string> prepath(lastpath);
     int p = 0;
     for( auto nstr : pathmap[start] ){
          if( p > 0 )//generate new path
              pathlist.push_back(prepath);
          pathreverse(pathmap, nstr, pathlist);
          p++;
     }
}
vector< vector<string> > findLadders(string start, string end, unordered_set<string> &dict){
      vector< vector<string> > pathlist;
      string tmp = start;
      start = end;
      end = tmp;
      int slen = start.size();
      int elen = end.size();
      if( slen != elen )
          return pathlist;
      dict.insert(start);
      dict.insert(end);
      //run bfs
      unordered_map<string, unordered_set<string>> pathmap;
      unordered_set<string> curset;
      curset.insert(start);
      dict.erase(start);
      unordered_set<string> adjset;
      bool find = false;
      while( !find && curset.size() > 0 ){
           unordered_set<string> preset(curset);
           curset.clear();
           for( auto pres : preset){
                if( pres == end ){//find it
                    find = true;
                    pathlist.push_back(vector<string>());
                    pathreverse(pathmap, end, pathlist);
                    break;
                }
                calAdj(pres, dict, adjset);
                curset.insert(adjset.begin(),adjset.end());//put in next layer
                for( auto nexts : adjset ){
                     pathmap[nexts].insert(pres); // record its parents
                }
           }
           for( auto vs : curset) // remove visited string
                dict.erase(vs);
      }
      return pathlist;
}
};