Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. 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.

It is also a BFS algorithm. Since there is no weight on each path, Dijkstra is not necessary.

There are some subtle details should be handled.

1. store the current shortest path when we visit a node.

2. update the shortest path when visiting a node

3. push adjacent nodes in the queue

```class Solution {
public:
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
//variable declaration
queue<string> q;
unordered_map<string, vector<vector<string>>> visitedPath;
vector<vector<string>> re;
vector<string> thisRe;
//extreme cases
if(start == end){
thisRe.push_back(start);
re.push_back(thisRe);
return re;
}
else if(isOneEditDistance(start, end)){
thisRe.push_back(start);
thisRe.push_back(end);
re.push_back(thisRe);
return re;
}
else{
//ordinary cases
q.push(start);
thisRe.push_back(start);
vector<vector<string>> paths;
paths.push_back(thisRe);
visitedPath[start] = paths;
while(!q.empty()){
string word = q.front();
q.pop();
if(isOneEditDistance(word, end)){
if(visitedPath.find(end) != visitedPath.end()){
//end is visited before
if(visitedPath[end][0].size() < visitedPath[word][0].size() + 1){
//previous path is shorter than current path
break;
}
else{
for(auto it = visitedPath[word].begin(); it != visitedPath[word].end(); it++){
vector<string> tmpPath = *it;
tmpPath.push_back(end);
visitedPath[end].push_back(tmpPath);
}
}
}
else{
//end is not visited before
visitedPath[end] = vector<vector<string>>();
for(auto it = visitedPath[word].begin(); it != visitedPath[word].end(); it++){
vector<string> tmpPath = *it;
tmpPath.push_back(end);
visitedPath[end].push_back(tmpPath);
}
}
}
//not the last step
else{
for(size_t i = 0; i < word.size(); i++){
for(char c = 'a'; c <= 'z'; c++){
if(word[i] == c) continue;
string tmps = word;
tmps[i] = c;
if(dict.find(tmps) != dict.end()){
//tmps exists in dict
if(visitedPath.find(tmps) != visitedPath.end()){
//tmps exists in visitedPath
if(visitedPath[tmps][0].size() < visitedPath[word][0].size() + 1){
//previous path to tmps is shorter than current path
continue;
}
else{
//previous path and current path have same length
for(auto it = visitedPath[word].begin(); it != visitedPath[word].end(); it++){
//vector<string>* it
vector<string> path = *it;
path.push_back(tmps);
visitedPath[tmps].push_back(path);
}
}
}
else{
//tmps not exist in visitedPath
q.push(tmps);
visitedPath[tmps] = vector<vector<string>>();
for(auto it = visitedPath[word].begin(); it != visitedPath[word].end(); it++){
//vector<string>* it
vector<string> path = *it;
path.push_back(tmps);
visitedPath[tmps].push_back(path);
}
}
}
else{
//tmp not exist in dict

}
}
}
}
}
return visitedPath.find(end) == visitedPath.end()?re:visitedPath[end];
}
}
bool isOneEditDistance(string a, string b){
int diff = 0;
for(size_t i = 0; i < a.size(); i++){
if(a[i] == b[i]){
continue;
}
else{
diff++;
}
}
return diff == 1? true: false;
}
};
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.