Word Ladder II [Leetcode]

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.

Solution: first do BFS to explore all possible transitions from start to end to build a DAG; and then do DFS to backtrack all possible paths from end to start according to the DAG.

class Solution {  
public:  
    //Back track all possible paths
    void buildPath(vector<vector<string>> &ret, unordered_map<string, vector<string>> &adjDAG, 
        vector<string> path, string cur, string start) {  
        if(cur==start){
            path.insert(path.begin(), cur);
            ret.push_back(path);
            return;
        }
        path.insert(path.begin(), cur);
        for(int i=0; i<adjDAG[cur].size(); ++i)
            buildPath(ret, adjDAG, path, adjDAG[cur][i], start);
    }  

    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 
        vector<vector<string>> ret;
        dict.insert(start);
        dict.insert(end);
        unordered_map<string, vector<string>> adjDAG; //child and parents.
        vector<unordered_set<string>> layers(2);
        int cur=0;
        int pre=1;
        layers[cur].insert(start);
        //Do BFS to build DAG
        while(!layers[cur].empty() && !layers[cur].count(end)){
            cur=!cur;
            pre=!pre;
            for(auto it=layers[pre].begin(); it!=layers[pre].end(); ++it)
                dict.erase(*it);
            layers[cur].clear();
            for(auto it=layers[pre].begin(); it!=layers[pre].end(); ++it){
                //Try all possible variants
                for(int j=0; j<(*it).size(); ++j){
                    for(char k='a'; k<='z'; ++k){
                        string tmp = (*it);
                        if(tmp[j]==k)
                            continue;
                        tmp[j]=k;
                        if(dict.find(tmp)!=dict.end()){
                            adjDAG[tmp].push_back(*it);
                            layers[cur].insert(tmp);
                        }
                    }
                }
            }
        }
        //No path found
        if(layers[cur].empty())
            return ret;
        //Some paths found
        vector<string> path;
        //Do DFS to build paths according to the DAG
        buildPath(ret, adj, path, end, start);
        return ret;
    }  
};