【题目】
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"]
]
Note:
- All words have the same length.
- All words contain only lowercase alphabetic characters.
【题意】
给定两个单词start和end, 一个词典，找到全部的最短转换序列。
几个注意事项：
1. 每次变换仅仅能改变一个字符
2. 变换的中间单词必须在词典中
3. 全部单词长度同样
4. 全部单词字符都小写
【思路】
思路和word Ladder是同样的，仅仅只是本题须要把左右的序列输出。
为了恢复转换序列在搜索的过程中，我们须要记录每一个可达单词的前继单词（所谓单词可达，就是start通过若干次字符变换后能够转换成当前单词）。
一旦我们找到end, 我们就能够通过前继恢复路径。这跟用dijkstra找最短路径的方法事实上非常相似。
【代码】
class Solution {
public:
void getSequences(vector<vector<string> >&result, vector<string>&sequence, string&start, string end, map<string, vector<string> >&percursors){
sequence.push_back(end);
if(start==end){
vector<string> v=sequence;
reverse(v.begin(), v.end());
result.push_back(v);
return;
}
//找end的前驱
vector<string> pres = percursors[end];
for(int i=0; i<pres.size(); i++){
getSequences(result, sequence, start, pres[i], percursors);
sequence.pop_back();
}
}
vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
vector<vector<string> > result;
if(start==end)return result;
//记录前驱的map
map<string, vector<string> > percursors;
//标记是否已经找到最短序列
bool isFind=false;
//交替存储相邻
queue<string> q1;
queue<string> q2;
q1.push(start);
//找前驱
while(!q1.empty() || !q2.empty()){
//存放当前层单词
set<string> words;
if(!q1.empty()){
while(!q1.empty()){
string curword=q1.front(); q1.pop();
for(int i=0; i<curword.length(); i++){
string tword=curword;
for(char c='a'; c<='z'; c++){
if(c!=curword[i]){
tword[i]=c;
//推断是否是end
if(tword==end){
isFind=true;
//保存前驱
percursors[tword].push_back(curword);
//保存当前层单词
words.insert(tword);
}
else if(dict.find(tword)!=dict.end()){
//假设tword在词典中。则保存它的前驱
percursors[tword].push_back(curword);
//保存当前层单词
words.insert(tword);
}
}
}
}
}
//将当前层的单词保存到q2
for(set<string>::iterator it=words.begin(); it!=words.end(); it++){
q2.push(*it);
dict.erase(*it);
}
}
else{
while(!q2.empty()){
string curword=q2.front(); q2.pop();
for(int i=0; i<curword.length(); i++){
string tword=curword;
for(char c='a'; c<='z'; c++){
if(c!=curword[i]){
tword[i]=c;
//推断是否是end
if(tword==end){
isFind=true;
//保存前驱
percursors[tword].push_back(curword);
//保存当前层单词
words.insert(tword);
}
else if(dict.find(tword)!=dict.end()){
//假设tword在词典中，则保存它的前驱
percursors[tword].push_back(curword);
//保存当前层单词
words.insert(tword);
}
}
}
}
}
//将当前层的单词保存到q1
for(set<string>::iterator it=words.begin(); it!=words.end(); it++){
q1.push(*it);
dict.erase(*it);
}
}
if(isFind)break;
}
//生成全部序列
vector<string>sequence;
getSequences(result, sequence, start, end, percursors);
return result;
}
};