Word Ladder II
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
http://www.lintcode.com/en/problem/word-ladder-ii/
Discussion
跟Word Ladder问题不同之处在于输出所有可行解。因此在BFS过程中，需要存储中间结果，用的是个unordered_map，key是string代表当前节点，
value是一个vector<string>用来记录从哪些节点可以到当前节点。
最后再根据这个map来trace出所有可行解。
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>> result;
unordered_set<string> current, next;
current.emplace(start);
unordered_set<string> isVisited;
unordered_map<string, vector<string> > father;
bool found = false;
while(current.empty() == false) {
for(auto word: current) {//去重
isVisited.emplace(word);
}
for(auto word: current) {
for(int i=0; i<word.size(); i++) {//扩展
string new_word = word;
for(char c='a'; c<='z'; c++) {
if(c == new_word[i])
continue;
swap(c, new_word[i]);//扩展状态
if(new_word == end) {
found = true;
father[new_word].push_back(word);//记录路径
break;
}
if(dict.find(new_word) != dict.end() &&
(isVisited.find(new_word) == isVisited.end())) {
//isVisited.emplace(new_word);
father[new_word].push_back(word);//记录路径
next.emplace(new_word);
}
swap(c, new_word[i]);//恢复
}
}
//DON'T BREAK HERE EVEN FOUND IS TRUE; -- FIND ALL SOLUTIONS. SO WE NEED TO CHECK OTHER WORDS IN CURRENT QUEUE.在当前层找到最优解了还不能停，因为当前层可能还有别的node也可以再改个letter就变成end
}
if(found == true) break;//这里要break因为在当前层找到解以后就不用再trace下一层了，因为要的是shortest path
current.clear();
current.swap(next);//更新current层，开始下次循环
}
if(found) {
vector<string> path;
genPath(father, path, start, end, result);
}
return result;
}
void genPath(unordered_map<string, vector<string> > &father, vector<string> &path,
string start, string curWord, vector<vector<string>> &result) {
path.push_back(curWord);
if(curWord == start) {
result.push_back(path);
reverse(result.back().begin(), result.back().end());//结果是反的，所以要逆序
} else {
for(int i=0; i<father[curWord].size(); i++) {
string tmp = father[curWord][i];
genPath(father, path, start, tmp, result);
}
}
path.pop_back();
}
};
这个题花了太多时间了，灰常的郁闷……刚开始我只是在Word Ladder的基础上增加map存储中间过程，但是……
- current和next用queue是不行的，因为在同一层也有可能出现重复的word，对于Word Ladder问题来说这一点是没关系的因为找到一个解返回level就可以了，而这个是要输出所有解。所以current next用的都是unordered_map，这样在emplace的时候就可以防止重复了。
- isVisited的更新也跟Word Ladder不一样，不能在next.emplace的时候update isVisited，而应该在开始遍历current层之前标记该层里面所有的word都是访问过的。这一点让我非常的费解。
下面这个solution就是用queue，死活只有77% test cases通过。。。
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>> result;
queue<string> current, next;
current.push(start);
unordered_set<string> isVisited;
unordered_map<string, vector<string> > father;
bool found = false;
while (current.empty() == false) {
queue<string> cpyCur (current);
while(cpyCur.empty() == false) {
string tmp = cpyCur.front();
cpyCur.pop();
isVisited.emplace(tmp);
}
while (current.empty() == false) {
string curStr = current.front();
current.pop();
for (int i = 0; i<curStr.size(); i++) {
string newStr = curStr;
for (char c = 'a'; c <= 'z'; c++) {
if (c == newStr[i])
continue;
swap(c, newStr[i]);
if (newStr == end) {
found = true;
father[newStr].push_back(curStr);
//isVisited.emplace(newStr);
break;
}
if (dict.find(newStr) != dict.end() && isVisited.find(newStr) == isVisited.end()) {
//isVisited.emplace(newStr);
father[newStr].push_back(curStr);
next.push(newStr);
}
swap(c, newStr[i]);
}
}
//DON'T BREAK HERE EVEN FOUND IS TRUE; -- FIND ALL SOLUTIONS. SO WE NEED TO CHECK OTHER WORDS IN CURRENT QUEUE.
}
if(found == true) break;
current.swap(next);
}
if (found) {
vector<string> path;
genPath(father, path, start, end, result);
}
return result;
}
void genPath(unordered_map<string, vector<string> > &father, vector<string> &path,
string start, string curWord, vector<vector<string>> &result) {
path.push_back(curWord);
if(curWord == start) {
result.push_back(path);
reverse(result.back().begin(), result.back().end());
} else {
for(int i=0; i<father[curWord].size(); i++) {
string tmp = father[curWord][i];
genPath(father, path, start, tmp, result);
}
}
path.pop_back();
}
};
下面这个方案是在update next的时候update isVisited，也是死活只有77% test cases通过。
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>> result;
unordered_set<string> current, next;
current.emplace(start);
unordered_set<string> isVisited;
unordered_map<string, vector<string> > father;
bool found = false;
while(current.empty() == false && found == false) {
for(auto word: current) {
for(int i=0; i<word.size(); i++) {
string new_word = word;
for(char c='a'; c<='z'; c++) {
if(c == new_word[i])
continue;
swap(c, new_word[i]);
if(new_word == end) {
found = true;
father[new_word].push_back(word);
break;
}
if(dict.find(new_word) != dict.end() &&
(isVisited.find(new_word) == isVisited.end())) {
isVisited.emplace(new_word);
father[new_word].push_back(word);
next.emplace(new_word);
}
swap(c, new_word[i]);
}
}
//DON'T BREAK HERE EVEN FOUND IS TRUE; -- FIND ALL SOLUTIONS. SO WE NEED TO CHECK OTHER WORDS IN CURRENT QUEUE.
}
//if(found == true) break;
current.clear();
current.swap(next);
}
if(found) {
vector<string> path;
genPath(father, path, start, end, result);
}
return result;
}
void genPath(unordered_map<string, vector<string> > &father, vector<string> &path,
string start, string curWord, vector<vector<string>> &result) {
path.push_back(curWord);
if(curWord == start) {
result.push_back(path);
reverse(result.back().begin(), result.back().end());
} else {
for(int i=0; i<father[curWord].size(); i++) {
string tmp = father[curWord][i];
genPath(father, path, start, tmp, result);
}
}
path.pop_back();
}
};
第二个实在不科学啊……绝望了……
强迫症又发作了，于是又去leetcode上提交了一下，比lintcode聪明，给出了错误的case：
Input: "red" "tax" ["ted","tex","red","tax","tad","den","rex","pee"]
Output: [["red","ted","tad","tax"],["red","rex","tex","tax"]]
Expected: [["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]red刚开始就在dict里，debug发现有可能在中间层又回到了red，因为red刚开始没有被标记为已访问。于是我在current开始之前加上了
if (dict.find(start) != dict.end()) { isVisited.emplace(start); }.然并卵。。。这个时候我的内心几乎是崩溃的。。。。于是我画出来状态转移图，继续debug
red
/ \
ted rex
/ \ /
tad tex
\ /
tax
我发现tex的父亲节点rex是不能在father里面记录下来的！！！！
因为ted-->tex的时候tex已经标记为visited了！！！！！
这就是为什不能在update next的时候更新isVisited，因为这个word还有可能被current层的其它node到达啊！！！你标记了visited，那其它node就到不了这个word了啊！！！！
这一切在Word Ladder问题里面是不存在的因为它不care是通过哪些node到达的tex，只要tex到达了路径长度就加一就完了啊！！！！
让我去哭一会儿……
回来再说一句，BFS里面的去存要非常小心，安全的做法是在产生next之前去存，不是在next产生的时候去存。因为在next产生的时候去存，不能保证current层里每一个node都不受影响。
Update
熟悉了以后再回过头看上面的分析。。。还是要熟！
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) {
unordered_set<string> visited;
unordered_set<string> level[2];
unordered_map<string, unordered_set<string> > ancestors;
int cur = 0;
level[cur].emplace(start);
while(level[cur%2].empty() == false) {
//chech if end has been found, make sure shortest
if(ancestors.find(end) != ancestors.end()) {
cur++;
break;
}
//mark current level as visited
for(auto const& s : level[cur%2]) {
visited.emplace(s);
}
//update ancestor, extend to next level
level[(cur+1)%2].clear();
for(auto const& s : level[cur%2]) {
for(int i=0; i<s.length(); i++) {
string tmp = s;
for(char c = 'a'; c<='z'; c++) {
tmp[i] = c;
if(dict.find(tmp) != dict.end() && visited.find(tmp) == visited.end()) {
ancestors[tmp].emplace(s);//s is one of tmp's ancestors
level[(cur+1)%2].emplace(tmp);
}
}
}
}
//continue next level
cur++;
}
//generate paths based on ancestors
vector<vector<string> > result;
vector<string> path;
GeneratePaths(start, end, path, ancestors, result);
return result;
}
void GeneratePaths(string start, string current, vector<string> &path,
unordered_map<string, unordered_set<string> > &ancestors,
vector<vector<string> > &all_paths) {
//a dfs method trace back from current to start
path.emplace_back(current);
if(current == start) {
all_paths.emplace_back(path);
reverse(all_paths.back().begin(), all_paths.back().end());//from start to end
} else {
//dfs current's ancestors
for(auto const& s : ancestors[current]) {
GeneratePaths(start, s, path, ancestors, all_paths);
}
}
path.pop_back();
}
};