Lintcode: Word Ladder II

Recreate a graph based on levels of adjacent nodes, then use backtracking.

Thought:
http://decomplexify.blogspot.com/2014/05/word-ladder-ii.html

good formatted java codes:
http://www.jiuzhang.com/solutions/word-ladder-ii/

good c++ version:(use goto however)
http://www.cnblogs.com/TenosDoIt/p/3443512.html




I modified the java version from jiuzhang to C++ version, cuz cannot find good version of c++ online
All tears TAT

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

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 vector<vector<string> > ladders; unordered_map<string, vector<string> > map; unordered_map<string, int> distance; dict.insert(start); dict.insert(end); bfs(map, distance, start, end, dict); vector<string> path; dfs(ladders, path, end, start, distance, map); return ladders; } private: void reverse(vector<string> &path){ stack<string> s; for(int i = 0; i < path.size(); i++){ s.push(path[i]); } for(int i = 0; i <path.size(); i++){ path[i] = s.top(); s.pop(); } } void dfs(vector<vector<string> > &ladders, vector<string> &path, string cur, string start, unordered_map<string, int> &distance, unordered_map<string, vector<string> > &map){ path.push_back(cur); if(cur == start){ reverse(path); ladders.push_back(path); reverse(path); }else{ for(int i = 0; i <map[cur].size(); i++){ if(distance.count(map[cur][i]) && distance[cur] == distance[map[cur][i]] + 1){ dfs(ladders, path, map[cur][i], start, distance, map); } } } path.pop_back(); } void bfs(unordered_map<string, vector<string> > &map, unordered_map<string, int> &distance, string start, string end, unordered_set<string> &dict){ queue<string> q; q.push(start); distance[start] = 0; while(!q.empty()){ string cur = q.front(); q.pop(); vector<string> nextList = expand(cur, dict); for(int i = 0; i < nextList.size(); i++){ map[nextList[i]].push_back(cur); //only record the minimux level, which is the element first appear,机智 if(!distance.count(nextList[i])){ distance[nextList[i]] = distance[cur] + 1; q.push(nextList[i]); } } } } vector<string> expand(string cur, unordered_set<string> &dict){ vector<string> expansion; for(int i = 0; i < cur.size(); i++){ char ch = cur[i]; for(char c = 'a'; c <= 'z'; c++){ if(c != ch){ cur[i] = c; if(dict.count(cur)){ expansion.push_back(cur); } cur[i] = ch; } } } return expansion; } };