题目描述
给定两个单词（初始单词和目标单词）和一个单词字典，请找出所有的从初始单词到目标单词的最短转换序列：
每一次转换只能改变一个单词
每一个中间词都必须存在单词字典当中
例如：
给定的初始单词start="hit"，
目标单词end ="cog"。
单词字典dict =["hot","dot","dog","lot","log"]
返回的结果为：
[↵ ["hit","hot","dot","dog","cog"],↵ ["hit","hot","lot","log","cog"]↵ ]注意：
题目中给出的所有单词的长度都是相同的
题目中给出的所有单词都仅包含小写字母
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"]↵ ]↵
class Solution {public:/* vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) { vector<vector<string>> paths; vector<string> path(1, start); if(start == end){ paths.push_back(path); return paths; } unordered_set<string> forward, backward; forward.insert(start); backward.insert(end); unordered_map<string, vector<string>> nexts; bool isForward = false; if(findLaddersHelper(forward, backward, dict, nexts, isForward)) getPath(start, end, nexts, path, paths); return paths; }private: bool findLaddersHelper(unordered_set<string> &forward, unordered_set<string> &backward, unordered_set<string> &dict, unordered_map<string, vector<string>> nexts, bool &isForward){ if(forward.empty()) return false; if(forward.size() > backward.size()) return findLaddersHelper(backward, forward, dict, nexts, isForward); //从words数较少的一边开始寻路 for(auto it=forward.begin(); it!=forward.end(); it++) dict.erase(*it); for(auto it=backward.begin(); it!=backward.end(); it++) dict.erase(*it); unordered_set<string> nextLevel; bool reach = false; for(auto it=forward.begin(); it!=forward.end(); ++it){ string word = *it; for(auto ch=word.begin(); ch!=word.end(); ++ch){ char tmp = *ch; for(*ch='a'; *ch<='z'; ++(*ch)){ if(*ch != tmp) //遍历除自身外的25个字母 if(backward.find(word) != backward.end()){ reach = true; //走到了末尾 isForward ? nexts[*it].push_back(word) : nexts[word].push_back(*it); } else if(!reach && dict.find(word) != dict.end()){ nextLevel.insert(word); isForward ? nexts[*it].push_back(word) : nexts[word].push_back(*it); } } *ch = tmp; } } return reach || findLaddersHelper(backward, nextLevel, dict, nexts, isForward); } void getPath(string beginWord, string &endWord, unordered_map<string, vector<string>> &nexts, vector<string> &path, vector<vector<string>> &paths){ if(beginWord == endWord) paths.push_back(path); else for(auto it=nexts[beginWord].begin(); it!=nexts[beginWord].end(); ++it){ path.push_back(*it); getPath(*it, endWord, nexts, path, paths); path.pop_back(); } }*/ vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) { vector<vector<string> > paths; vector<string> path(1, start); if (start == end) {//首位words相同 paths.push_back(path); return paths; } unordered_set<string> forward, backward; forward.insert(start); backward.insert(end); unordered_map<string, vector<string> > nexts; //存储路径的矩阵 bool isForward = false; if (findLaddersHelper(forward, backward, dict, nexts, isForward)) getPath(start, end, nexts, path, paths); return paths; }private: bool findLaddersHelper( unordered_set<string> &forward, unordered_set<string> &backward, unordered_set<string> &dict, unordered_map<string, vector<string> > &nexts, bool &isForward) { isForward = !isForward; //反转方向标志？？ if (forward.empty()) return false; if (forward.size() > backward.size()) return findLaddersHelper(backward, forward, dict, nexts, isForward);//从words数较少的一边开始寻路 for (auto it = forward.begin(); it != forward.end(); ++it) //已放入前向 后向数组中的words从dict去除 dict.erase(*it); for (auto it = backward.begin(); it != backward.end(); ++it) dict.erase(*it); unordered_set<string> nextLevel; bool reach = false; //寻路未完成 for (auto it = forward.begin(); it != forward.end(); ++it) {//广度遍历前向数组中的每一个分支 string word = *it; for (auto ch = word.begin(); ch != word.end(); ++ch) { char tmp = *ch; for (*ch = 'a'; *ch <= 'z'; ++(*ch))//遍历除自身外的25个字母 if (*ch != tmp) if (backward.find(word) != backward.end()) { //前后向数组成功相接 reach = true; //寻路完成 isForward ? nexts[*it].push_back(word) : nexts[word].push_back(*it); } else if (!reach && dict.find(word) != dict.end()) { //未到达 且 字典中有需要的words nextLevel.insert(word); //将新产生的分支放入临时数组，用于下次递归调用 isForward ? nexts[*it].push_back(word) : nexts[word].push_back(*it); } *ch = tmp; } } return reach || findLaddersHelper(backward, nextLevel, dict, nexts, isForward); } void getPath( string beginWord, string &endWord, unordered_map<string, vector<string> > &nexts, vector<string> &path, vector<vector<string> > &paths) { if (beginWord == endWord) //走到了，将path中的值压入paths paths.push_back(path); else for (auto it = nexts[beginWord].begin(); it != nexts[beginWord].end(); ++it) { path.push_back(*it); getPath(*it, endWord, nexts, path, paths); path.pop_back(); //每退出一次递归，将该层压入的值弹出 } }};