Leetcode---Word Ladder II

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.

这道题是要求：给一个起点S和终点E，输出所有最短路径。
BFS时，当你给每个节点加了前驱，你也无法输出所有最短路径，因为有这样的节点存在：

在上图中，B有两个前驱节点A和C，因此存储前驱时，必然存在其中一个覆盖掉另一个的情况。
所以我们需要存储所有的前驱，这里有几个情况需要考虑：
1. 第k+1层需要避免把第k层的节点再添加到队列中
2. 当一个节点A需要把和它相邻的另一个节点B加入队列时，需要"前驱为A的路径上B的深度值<=已经被加入队列的B的深度值“, 这是因为BFS总是先发现最短路径，所以先加入队列的B的深度值一定是最小深度值，但是有可能有同样是最小深度值，但是不同的前驱需要存储。可以看上面那个图帮助理解。
这里面还有个小trick：当需要vector存储两个以上的item时，写一个struct帮助存储。
code如下，但是。。。TLS！！！

public:
    struct S{
        string me;
        int pre;
        int depth;
        S(string& _me,int _pre,int _depth ){
            me=_me;
            pre=_pre;
            depth=_depth;
        }
    };
    int lookslike(string s1, string s2){
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1[i] != s2[i]) {
                diff++;
                if (diff >= 2)
                    return 2;
            }
        }
        return diff;
    }
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        vector<vector<string>> result;
        if(0==lookslike(start,end)){
                return result;
        }
        if(1==lookslike(start,end)){
                vector<string> str;
                str.push_back(start);
                str.push_back(end);
                result.push_back(str);
                return result;
        }
        dict.erase(start);
        dict.erase(end);
        deque<S> Q;
        vector<S> V;
        unordered_map<string,bool> map;
        unordered_map<string,int> map2;
        Q.push_back(S(start,-1,1));
        map2.insert({start,1});
        bool flag=false;
        while(!Q.empty()){
            S a = Q.front();
            Q.pop_front();
            map2.erase(a.me);
            if(flag==false){
                V.push_back(a);
                map.insert({a.me,true});
            }
            string me=a.me;
            int pre=a.pre;
            int depth=a.depth;
            if(1==lookslike(me,end)){
                //cout<<Q.size()<<" "<<V.size()<<endl;
                flag=true;
                vector<string> str;
                str.push_back(end);
                str.push_back(me);
                int x=pre;
                while(x!=-1){
                    str.push_back(V[x].me);
                    x=V[x].pre;
                }
                reverse(str.begin(),str.end());
                result.push_back(str);
                continue;
            }
            else if(flag==false){
                string tmp=me;
                for(int i=0;i<tmp.length();i++){
                    for(char c='a';c<='z';c++){
                        tmp.replace(i,1,1,c);
                        if(dict.find(tmp)!=dict.end()){
                            if(map.find(tmp)==map.end()){
                                    //if(depth+1<=getdepth(Q,tmp))
                                    if((map2.find(tmp)!=map2.end() && depth+1<=map2[tmp]) || map2.find(tmp)==map2.end()){
                                        Q.push_back(S(tmp,V.size()-1,depth+1));
                                        map2.insert({tmp,depth+1});
                                    }
                            }
                        }
                    }
                    tmp=me;
                }
            }
        }
        return result;
    }