题目描述
给定两个单词（初始单词和目标单词）和一个单词字典，请找出所有的从初始单词到目标单词的最短转换序列：每一次转换只能改变一个单词每一个中间词都必须存在单词字典当中例如：给定的初始单词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(); //每退出一次递归，将该层压入的值弹出 } }};
