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.
和Word Ladder不同的地方在于可能多个父节点公用一个子节点。将父节点都记录下来即可。
class Solution {
public:
struct info{
info(){}
info(int level,int index){
m_level=level;
m_index=index;
}
int m_level;
int m_index;
};
void Path(vector<vector<string> >* ret,vector<string>* path,const vector<vector<int> >&father,const vector<string>& record,int index,int count){
(*path)[count]=record[index];
if(count==0){
ret->push_back(*path);
}
else{
for(int i=0;i<father[index].size();i++){
Path(ret,path,father,record,father[index][i],count-1);
}
}
}
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map<string,info> m;
int qhead=0;
vector<string> record;
vector<int> tails;
vector<vector<int> >father;
int index=0;
m[start]=info(0,0);
record.push_back(start);
father.resize(father.size()+1);
int min_v=2147483647; while(qhead<record.size()!=0){
int currentIndex=index;
string s=record[qhead];
for(int i=0;i<s.length();i++){
char c=s[i];
for(int j='a';j<'z';j++){
if(j!=c){
s[i]=j;
if(s==end){
int level=m[record[qhead]].m_level+1;
if(level<min_v){
min_v=level;
tails.clear();
tails.push_back(qhead);
}
else if(level==min_v){
tails.push_back(qhead);
}
}
else if(dict.find(s)!=dict.end()){
if(m.find(s)==m.end()){
index++;
m[s]=info(m[record[qhead]].m_level+1,index);
father.resize(father.size()+1);
father[index].push_back(qhead);
record.push_back(s);
}
else{
info sinfo=m[s];
info tinfo=m[record[qhead]];
if(sinfo.m_level==tinfo.m_level+1){
father[sinfo.m_index].push_back(qhead);
}
}
}
}
s[i]=c;
}
}
qhead++;
}
if(min_v==2147483647){
return vector<vector<string> >(); } vector<vector<string> >ret;
vector<string>path; path.resize(min_v+1);
path[min_v]=end;
for(int i=0;i<tails.size();i++){
Path(&ret,&path,father,record,tails[i],min_v-1);
}
return ret;
}
};