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;
    }
};