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

Note

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

Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return

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

 
class Solution {
public:
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return a list of lists of string
      */
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        unordered_map<string, set<string>> backPath;
        
        // BFS, each round is a generation
        set<string> generations[2];
        int curGen = 0;
        
        generations[curGen].insert(start);
        while(dict.size() > 0 && generations[curGen % 1].size() > 0) 
        {
            // end is in current generation, stop
            if (backPath.count(end) == 1) 
              break;

           // clear words from the dictionary to avoid it' apear in future generation again
            for(string word : generations[curGen & 1]) 
                dict.erase(word);
                
            generations[(curGen+1) & 1].clear();
            for(string from : generations[curGen & 1]) {
                string newWord = from;
                for(int i = 0; i < newWord.length(); i++) {
                    char origC = from[i];
                    for(char c = 'a'; c <= 'z'; c++) {
                        newWord[i] = c;
                        if (dict.count(newWord) == 1) 
                        {
                           backPath[newWord].insert(from);
                           generations[(curGen+1) & 1].insert(newWord);
                        }
                    }
                    newWord[i] = origC;
                }
            }
            
            curGen += 1;
        }
        
        vector<vector<string>> output;
        vector<string> temp;
        buildPath(backPath, temp, end, output);
        return output;
    }
    
    void buildPath(
        unordered_map<string, set<string>> &backPath, 
        vector<string> &temp,
        string end, 
        vector<vector<string>> &output)
    {
        temp.push_back(end);
        if (backPath.count(end) != 1) {
            vector<string> path = temp;
            reverse(path.begin(), path.end());
            output.push_back(path);
        }
        else {
            for(string word: backPath[end]) 
               buildPath(backPath, temp, word, output); 
        }
        temp.pop_back();
    }
};