126. Word Ladder II (Hard)

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:

beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"]

Return

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

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20): The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution 1: BFS 482ms

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict, words;
        for (string& w: wordList) dict.insert(w);
        if (!dict.count(endWord)) return {};

        vector<string> p; p.push_back(beginWord);
        queue<vector<string>> paths;
        paths.push(p);
        vector<vector<string>> res;
        int level = 1, minlevel = INT_MAX;
        while (!paths.empty()) {
            vector<string> path = paths.front(); paths.pop();
            if (path.size() > level) {
                // delete all the words in prev level
                for (string w: words) dict.erase(w);
                words.clear();
                level = path.size();
                if (level > minlevel) break;
            }

            string last = path.back();
            for (int i = 0; i < last.size(); ++i) {
                string newLast = last;
                for (char c = 'a'; c <= 'z'; ++c) {
                    newLast[i] = c;
                    if (dict.count(newLast)) {
                        words.insert(newLast);
                        vector<string> nextPath = path;
                        nextPath.push_back(newLast);
                        if (newLast == endWord) {
                            res.push_back(nextPath);
                            minlevel = level;
                        } else paths.push(nextPath);
                    }
                }
            }
        }
        return res;
    }
};

Solution 2: BFS+DFS 135ms

class Solution {
    void dfs(unordered_map<string,vector<string>>& next, string& end, string prev, vector<string>& path, vector<vector<string>>& res) {
        if (prev == end) { res.push_back(path); return;}
        for (auto& cur: next[prev]) {
            path.push_back(cur);
            dfs(next, end, cur, path, res);
            path.pop_back();
        }

    }
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict;
        for (auto& w: wordList) dict.insert(w);
        if (!dict.count(endWord)) return {};

        unordered_map<string,vector<string>> next; // Neighbors for every node
        unordered_map<string,int> dist; // Distance of every node from the start node
        queue<string> q; q.push(beginWord);
        dist[beginWord] = 0;
        int n = beginWord.size();


        while (!q.empty()) {
            int cnt = q.size();
            bool foundEnd = false;

            for (int i = 0; i < cnt; ++i) { // curlevel
                string curWord = q.front(); q.pop();
                int curStep = dist[curWord]+1;
                dict.erase(curWord);
                bool foundEndwithCurWord = false;
                for (int j = 0; j < n; ++j) {
                    string newWord = curWord;
                    for (char c = 'a'; c <= 'z'; ++c) {
                        newWord[j] = c;
                        if (dict.count(newWord)) {

                            if (!dist.count(newWord) || dist[newWord] == curStep) 
                                next[curWord].push_back(newWord);
                            // found end -> shortest path, no need to loop the rest
                            if (curWord == endWord) {
                                foundEndwithCurWord = true;
                                foundEnd = true;
                                next[curWord] = {endWord};
                                break;
                            }

                            if (!dist.count(newWord)) { // internal node: Check if visited
                                dist[newWord] = curStep;
                                q.push(newWord);
                            }

                        }
                    }
                    if (foundEndwithCurWord) break;
                }
            }

            if (foundEnd) break;

        }

        /*
        for (auto& a: next) {
            cout << a.first << ": ";
            for (auto& b: a.second) {
                cout << b << ", ";
            }
            cout << endl;
        }*/

        vector<vector<string>> res;
        vector<string> path = {beginWord};
        dfs(next, endWord, beginWord, path, res);
        return res;
    }
};

Solution 3: 2 End BFS

In order to reduce the running time, we should use two-end BFS to slove the problem. 88ms! Accepted c++ solution with two-end BFS. 68ms for Word Ladder and 88ms for Word Ladder II