Word Ladder II

Word Ladder II

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

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

Note

• All words have the same length.
• All words contain only lowercase alphabetic characters.

Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

--------------------------- thinking ----------------------------
Since we need to print all pathes, we cannot simply check if a node is visited or not to return
Instead, we need to check if a node is on the same depth of the shorted path.
--------------------------- codes -------------------------------
class Solution {
public:
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return a list of lists of string
      */
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        // write your code here
        unordered_map<string, int> visited;
        unordered_map<string, vector<string>> parent;
        queue<string> que;
        que.push(start);
        visited[start] = 1;
        //BSF
        int min_depth = INT_MAX;
        while (!que.empty()) {
            string cur = que.front();
            que.pop();
            if (visited[cur] == min_depth) {
                break;
            } else {
                for (int i = 0; i < cur.size(); i++) {
                    for (char chr = 'a'; chr <= 'z'; chr++) {
                        if (chr != cur[i]) {
                            string str(cur);
                            str[i] = chr;
                            if (dict.find(str) == dict.end()) {
                                continue;
                            }
                            if (str.compare(end) == 0) {
                                min_depth = visited[cur] + 1;
                            }
                            if (visited.find(str) == visited.end() || visited[str] == visited[cur]+1) {
                                if (visited.find(str) == visited.end()) {
                                 //dont' push node several times, which will cause duplications          
                                    que.push(str);
                                    visited[str] = visited[cur]+1;
                                }
                                if (parent.find(str) == parent.end()) {
                                    vector<string> par(1, cur);
                                    parent[str] = par;
                                } else {
                                    parent[str].push_back(cur);
                                }
                            }
                        }
                    }
                }
            }
        }
        return buildResult(parent, start, end);
    }
    vector<vector<string>> buildResult(unordered_map<string, vector<string>> &parent, string &start, string &end) {
        vector<vector<string>> result;
        if (end.compare(start) == 0) {
            result.push_back(vector<string>(1, end));
            return result;
        }
        for (int i = 0; i < parent[end].size(); i++) {
            vector<vector<string>> tmp_result = buildResult(parent, start, parent[end][i]);
            for (int j = 0; j < tmp_result.size(); j++) {
                vector<string> ele = tmp_result[j];
                ele.push_back(end);
                result.push_back(ele);
            }
        }
        return result;
    }
};