AM 121. Word Ladder II

Code(Language:C++)

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) {
        // write your code here
       // BFS找最短路径，然后依据最短路径DFS找所有可能。
       //剩下的就看实现了
       // Let's go!!!
       unordered_map<string, vector<string>> next; //建立graph，一个点指向哪些点（有connection）
       unordered_map<string, int> steps; // 每个点在path上距离起始点的距离。
       
       vector<vector<string>> res; 
       dict.insert(end); 
       if(dict.size() == 0){
           return res; 
       }
       const int sLen = start.size(); 
       int dist = 1; 
       std::queue<string> q;
       q.push(start); 
       //dict.erase(start);
       steps[start] = 1; 
       while(!q.empty()){
           int sizeQ = q.size(); 
           dist++; 
           int breakFlag = 0; 
           for(int i = 0; i < sizeQ; i++){
               string oldTemp = q.front();
               q.pop(); 
               if(oldTemp == end){
                   breakFlag = 1; 
                   break; 
               }
               string temp = oldTemp; 
               // find match for each char 
               for(int j = 0; j < sLen; j++){
                   char oldChar = temp[j]; 
                   for(char c = 'a'; c <= 'z'; c++){
                       if(oldChar == c){
                           continue; 
                       }
                       temp[j] = c; 
                       // 核心在这里
                       if(dict.find(temp) != dict.end()){
                           if(steps.find(temp) == steps.end()){
                              q.push(temp);
                              //steps[temp] = steps[oldTemp] + 1;
                              steps[temp] = dist; 
                           }
                           next[oldTemp].push_back(temp); 
                       }
                   }
                   temp[j] = oldChar; 
               }

           }
           if(breakFlag){
               break; 
           }
       }
           vector<string> resElem; 
           resElem.push_back(start); 
           dfs(start, end, next, steps, res, resElem);
           return res; 
    }
    void dfs(string &start, string &end, unordered_map<string, vector<string>> &next, unordered_map<string,int> &steps, vector<vector<string>> &res, vector<string> &resElem){
        if(start == end){
            res.push_back(resElem); 
            return; 
        }
        for(auto str : next[start]){
            if(steps[str] == steps[start] + 1){
            resElem.push_back(str);
            dfs(str, end, next, steps, res, resElem);
            resElem.pop_back(); 
            }
        }
    }
};