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

 1 class Solution {
 2 public:
 3     vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
 4         map<string, vector<string>> traces; // If A->C and B->C, then traces[C] contains A and B.
 5                                             // This is used for recovering the paths.
 6         vector<unordered_set<string>> level(2);
 7         int cur = 0;
 8         int prev = 1;
 9         level[cur].insert(start);
10         dict.insert(end);
11 
12         while (true)
13         {
14             prev = !prev;
15             cur = !cur;
16             level[cur].clear();
17 
18             // remove visited words. IMPORTANT!
19             for (unordered_set<string>::iterator it = level[prev].begin(); it != level[prev].end(); ++it)
20                 dict.erase(*it);
21 
22             for (unordered_set<string>::iterator it = level[prev].begin(); it != level[prev].end(); ++it)
23             {
24                 string word = *it;
25                 for (size_t i = 0; i < word.size(); i++) {
26                     char before = word[i];
27                     for (char c = 'a'; c <= 'z'; c++) {
28                         if (c == before)
29                             continue;
30                         word[i] = c;
31                         if (dict.find(word) != dict.end()) {
32                             traces[word].push_back(*it);
33                             level[cur].insert(word);
34                         }
35                     }
36                     word[i] = before;
37                 }
38             }
39 
40             if (level[cur].empty() || level[cur].count(end) > 0)
41                 break;
42         }
43 
44         vector<vector<string>> res;
45         vector<string> onePath;
46         if (!traces.empty())
47             buildResult(traces, res, onePath, end);
48 
49         return res;
50     }
51 
52     void buildResult(map<string, vector<string>> &traces, vector<vector<string>> &res, vector<string> &onePath, string word)
53     {
54         if (traces.count(word) == 0)
55         {
56             vector<string> copy(onePath);
57             copy.push_back(word);
58             reverse(copy.begin(), copy.end());
59             res.push_back(copy);
60             return;
61         }
62 
63         const vector<string> &s = traces[word];
64         onePath.push_back(word);
65         for (vector<string>::const_iterator it = s.begin(); it != s.end(); ++it)
66             buildResult(traces, res, onePath, *it);
67         onePath.pop_back();
68     }
69 };