单词变换路径 Word Ladder II

这一问题是《单词变换距离 Word Ladder （无权图的最短路径）》的引申问题。

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"]
  ]

思路：上一问题只要求得需要多少次变换能够从A单词到达B单词，当时使用的是BFS算法求得最短路径。现在的问题是，要求得所有可能的最短路径。因此，问题的难点在于，如何在BFS的过程当中记录路径。

BFS是层序遍历的，没办法直接去记录深度路径。因此，要把问题稍微转化一下，在BFS的过程中，记录每个单词在层序遍历树中的父节点，也就是在最短路径中前驱结点。当遇到目标单词end时，之后层次的遍历就不再进行了（当前所在层次一定要遍历完，因为同一层次可能有多种的最短路径）。

得到了这些结点的前驱结点（没有求得前驱结点的字符串一定不在最短路径上）之后，我从目标节点end反向查找前驱，就一定能找到出发结点start，并且这一过程中遇到的所有分支都是有效的路径。

class Solution {
public:

//宽度优先遍历：寻找最短路径，同时记录前驱单词
int bfs(string start, string end, unordered_set<string> &dict, map<string, unordered_set<string>> &prepath)
{
dict.erase(start);
dict.insert(end);
int stop = 0;
int cur = 1;

set<string> nextlevel; 
queue<string> que;  
queue<int> level; //和que一直伴随着，记录当前的层次。

level.push(cur);
que.push(start);

vector<string> del;
while(!que.empty())  
{  
string now = que.front(); // get string
que.pop();

if(cur != level.front())
{
nextlevel.clear();
for(int i=0;i<del.size();i++) //新层次开始时，才会把上一次用过的单词删掉
dict.erase(del[i]);
del.clear();
}
cur = level.front(); //get level
level.pop();

if(stop != 0 && stop != cur) //剪枝：若找到end，则下一层不再看
return stop;

for(int i=0;i<start.length();i++)  { 
for(int j=0;j<26;j++)  
{  
string next = now;  next[i] = 'a' + j;
if(now != next && dict.find(next) != dict.end())  
{
prepath[next].insert(now); // Remember back path

if(next == end) 
stop = cur;

del.push_back(next);
if(nextlevel.find(next) == nextlevel.end()) //优化：下一层中不重复记录
{
que.push(next);
level.push(cur+1); 
}
nextlevel.insert(next);
}
}  
}
}
return 0;
}
//由前驱单词backtrack生成所有路径
void backtrack(string now, vector<string> &path, string start, vector<vector<string>> &re, map<string, unordered_set<string>> &prepath)
{
if(now == start)
{
reverse(path.begin(), path.end());
re.push_back(path);
reverse(path.begin(), path.end());
return;
}
unordered_set<string> s = prepath[now];
unordered_set<string>::iterator it = s.begin();
for(;it!=s.end();it++)
{
path.push_back(*it);
backtrack(*it, path, start, re, prepath);
path.pop_back();
}
}
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {

vector<vector<string>> re;
map<string, unordered_set<string>> prepath;
//首先bfs
int level = bfs(start, end, dict, prepath);
if(level == 0)
return re;

//其次backtrack
vector<string> path;
path.push_back(end);
backtrack(end, path, start, re, prepath);
return re;
}

};

秒客网

单词变换路径 Word Ladder II

相关文章