Word Ladder II

题目：

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
All words have the same length.
All words contain only lowercase alphabetic characters.

分析：

这题目和ladder I的区别在于，不需要记录步数，而是需要枚举所有可能的path，具体思路如下：

1. bfs获取邻接表，同时还要开另外一个hash记录每一个点的stepcount
2. dfs从后往前做，每次dfs加入end，然后用上一步的end继续递归，注意条件是stepcount减少1

值得注意的地方包括：

因为需要一个完整的图来做这个，所以要把start和end放到字典里面
两个hash要提前开好，虽然都没有差，但是最好对他们进行初始化

这是一道综合训练的大题目，100行代码，并不容易写，需要重复练习。

解法：

class Solution {
public:
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return a list of lists of string
      */

    void dfs(string start, 
                string end, 
                unordered_map<string, vector<string> > &map, 
                unordered_map<string, int> &distance, 
                vector<string> path, 
                vector<vector<string> > &res) {
        // important, dfs is from end to start            
        path.push_back(end);

        if (end == start) {
            reverse(path.begin(), path.end() );
            res.push_back(path);
            reverse(path.begin(), path.end() );
            return;
        }

        vector<string> temp = map[end];
        for (int i = 0; i < temp.size(); i++) {
            if(distance[temp[i] ] == distance[end] - 1) {
                dfs(start, temp[i], map, distance, path, res);
            }
        }

    }  

    void bfs(string start, 
                string end, 
                unordered_set<string> &dict, 
                unordered_map<string, vector<string> > &map, 
                unordered_map<string, int> &distance) {

        queue<string> Q;
        Q.push(start);

        while (!Q.empty() ) {
            string word = Q.front();
            Q.pop();
            // get the next visit list
            vector<string> nextList;
            for (int j = 0; j < word.size(); j++) {
                char oldChar = word[j];
                for (char c = 'a'; c < 'z'; c++) {
                    if (c == oldChar) {
                        continue;
                    }
                    word[j] = c;
                    if (dict.find(word) != dict.end() ) {
                        nextList.push_back(word);
                    }
                }
                word[j] = oldChar;
            }
            map[word] = nextList;
            // avoid revisiting and count distance
            for (int i = 0; i < nextList.size(); i++) {
                if (distance.find(nextList[i]) == distance.end() ) {
                    distance[nextList[i] ] = distance[word] + 1;
                    Q.push(nextList[i]);
                }
            }
            // to safe time
            if (word == end) {
                break;
            }
        }
    }  

    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        // write your code here
        vector<vector<string> > res;
        if (start.size() == 0 || end.size() == 0 || dict.size() == 0) {
            return res;
        }
        if (start == end) {
            vector<string> temp;
            temp.push_back(start);
            res.push_back(temp);
            return res;
        }
        // important
        dict.insert(start);
        dict.insert(end);

        unordered_map<string, vector<string> > map;
        unordered_map<string, int> distance;

        bfs(start, end, dict, map, distance);
        vector<string> path;
        dfs(start, end, map, distance, path, res);
        return res;
    }
};