Word Ladder II

来源：Leetcode

原帖：https://oj.leetcode.com/problems/word-ladder-ii/

题目：
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that: Only one letter can be changed at a time. 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.
Solution: Idea is from blog: http://blog.csdn.net/niaokedaoren/article/details/8884938

代码：

 class Solution {  
 public:  
     vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {  
     // If A->C and B->C, then traces[C] contains A and B. This is used for recovering the paths.  
     unordered_map<string, vector<string>> traces;   
     queue<string> q;  
     q.push(start);  
     bool found = false;  
     while (!q.empty()) {  
       int size = q.size();  
       unordered_set<string> level;  
       for (int i = 0; i < size; ++i) {  
         string word = q.front(); q.pop();  
         string nextWord = word;  
         for (size_t j = 0; j < nextWord.size(); ++j) {  
           char before = nextWord[j];  
           for (char c = 'a'; c <= 'z'; c++) {  
             if (c == before) continue;  
             nextWord[j] = c;  
             if (nextWord == end)  
               found = true;  
             if (nextWord == end || dict.find(nextWord) != dict.end()) {  
               traces[nextWord].push_back(word);  
               level.emplace(nextWord);  
             }  
           }  
           nextWord[j] = before;  
         }     
       }  
       if (found) break;  
       for (auto it = level.begin(); it != level.end(); it++) {  
         q.push(*it);  
         dict.erase(*it);  
       }  
     }  
     vector<vector<string> > result;  
     vector<string> onePath;  
     if (!traces.empty()) {  
       buildResult(traces, result, onePath, end, start);        
     }  
     return result;  
   }  
   
   // backtracking to target (start word), then reverse the root->leaf order  
   // DFS  
   void buildResult(unordered_map<string, vector<string> > &traces, vector<vector<string>> &result,   
            vector<string> &onePath, string word, const string &target) {  
     if (word == target) { // word = start word   
       vector<string> copy(onePath);  
       copy.push_back(word);  
       reverse(copy.begin(), copy.end());  
       result.push_back(copy);  
       return;  
     }  
     vector<string> &s = traces[word];  
     onePath.push_back(word);  
     for (int i = 0; i < s.size(); ++i) {  
       buildResult(traces, result, onePath, s[i], target);  
     }  
     onePath.pop_back();  
   }    
 };