Given two words (startandend), and a dictionary, find all shortest transformation sequence(s) fromstarttoend, such that:
Only one letter can be changed at a timeEach 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.看了Discuss里面的题解，https://leetcode.com/discuss/9523/share-two-similar-java-solution-that-accpted-by-oj
自己改成了C++版本，具体的思路就是把每个string当做一个点，先BFS找到边，然后DFS找路径，，感觉有点像某道什么素数路径的题。
class Solution {public:vector<vector<string> > ans; // answervector<string> backtraceList; // list for backtracing, maybe an answermap<string, vector<string> > edges; // treat every string as a pointstring st; // start stringstring ed; // end stringunordered_set<string> visit; // BFS visitunordered_set<string> unvisit; // BFS unvisitvector<vector<string>> findLadders(string start, string end, unordered_set<string> & dict) {ans.clear();backtraceList.clear();edges.clear();if (dict.size() == 0) return ans;st = start;ed = end;visit.clear();unvisit = dict;BFS(); // bfs makes graphDFS(ed); // dfs find roads(from end to start)return ans;}void BFS() {int cur = 1; // current points to checkint next = 0; // next points to checkint l; // the length of each wordbool found = false;queue<string> q;q.push(st);unvisit.insert(ed);unvisit.erase(st); // maybe there is another start string in the dictwhile (!q.empty()) {string w = q.front();q.pop();cur–;l = w.size();for (int i = 0; i < l; i++) {char originalChar = w[i];string nw = w;for (char c = 'a'; c <= 'z'; c++) {nw[i] = c;if (unvisit.find(nw) != unvisit.end()) { // an unvisited wordif (visit.find(nw) == visit.end()) { // there is no this word in visitvisit.insert(nw);next++; // more word to visit next timeq.push(nw);}map<string, vector<string> >::iterator iter = edges.find(nw);if (iter != edges.end()) { // a new point of an existed edge(*iter).second.push_back(w);}else { // a new edgevector<string> temp;temp.push_back(w);edges[nw] = temp;}if (nw == ed) found = true;}}w[i] = originalChar;}if (cur == 0) {if (found) break;cur = next;next = 0;unordered_set<string>::iterator iter = visit.begin();for (; iter != visit.end(); iter++) unvisit.erase(*iter);visit.clear();}}}void DFS(string w) {if (w == st) { // find start stringvector<string> temp;temp.push_back(st);for (int i = 0, s = backtraceList.size(); i < s; i++)temp.push_back(backtraceList[s – i – 1]);ans.push_back(temp);return;}backtraceList.push_back(w);map<string, vector<string> >::iterator iter = edges.find(w);if (iter != edges.end()) {int s = iter->second.size();for (int i = 0; i < s; i++) DFS(iter->second[i]);}backtraceList.pop_back();}};
我不敢说我明天便可以做一个快乐的人，面朝大海春暖花开。
