leetcode24:word-ladder-ii

题目描述

给定两个单词（初始单词和目标单词）和一个单词字典，请找出所有的从初始单词到目标单词的最短转换序列：

每一次转换只能改变一个单词

每一个中间词都必须存在单词字典当中

例如：

给定的初始单词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(); //每退出一次递归，将该层压入的值弹出

}

};

巴特西

leetcode24:word-ladder-ii

题目描述

最新文章

热门文章