LeetCode 126. Word Ladder II 单词接龙 II(C++/Java)

题目：

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

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

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.

Example 1:

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

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

Example 2:

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

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

分析：

这道题是LeetCode 127. Word Ladder 单词接龙(C++/Java)的扩展，要找出所有最短转换序列。

还是利用BFS，在每一次搜索的时候都要将单词之间的转换记录下来，利用map进行存储，例如

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

hot可以改变一个字符转换为dot和lot，可以将单词和由这个单词扩展的单词列表存进map中，方便我们后续来进行路径构建。

此外我们要在每一层搜索前将单词从由单词序列构建的字典中删除掉，而不是在找到一个单词就删除。而且有的单词可能会成为多个单词的扩展，例如hot和dot都可以扩展为lot，所以如果当前循环中没有找到结果，所有有可能构建路径的单词都要存进map中，在这一轮搜索完毕后，再将它们从字典中删除。

程序：

C++

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict;
        vector<vector<string>> res;
        for(string s:wordList)
            dict.insert(s);
        if(!dict.count(endWord))
            return {};
        dict.erase(endWord);
        unordered_set<string> p{beginWord}, q;
        unordered_map<string, vector<string>> children;
        int l = beginWord.length();
        bool find = false;
        while(!p.empty() && !find){
            for(string s:p)
                dict.erase(s);
            for(string str:p){
                string word = str;
                for(int i = 0; i < l; ++i){
                    char ch = word[i];
                    for(int j = 'a'; j < 'z'; ++j){
                        if(ch == j)
                            continue;
                        word[i] = j;
                        if(word == endWord){
                            find = true;
                            children[str].push_back(word);
                        }else{
                            if(dict.count(word) && !find){
                                q.insert(word);
                                children[str].push_back(word);
                            }
                        }
                    }
                    word[i] = ch;
                }
            }
            p.clear();
            swap(p, q);
        }
        if(find){
            vector<string> path{beginWord};
            bfs(res, children, path, beginWord,endWord);
        }
        return res;
    }
private:
    void bfs(vector<vector<string>> &res,
            unordered_map<string, vector<string>> &children,
            vector<string> path,
            string beginWord, string endWord){
        if(beginWord == endWord){
            res.push_back(path);
            return;
        }
        auto it = children.find(beginWord);
        if(it == children.end()) return;
        for(string word:it->second){
            path.push_back(word);
            bfs(res, children, path, word, endWord);
            path.pop_back();
        }
    }
};

Java

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        List<List<String>> res = new ArrayList<>();
        if(!dict.contains(endWord))
            return res;
        Set<String> p = new HashSet<>();
        p.add(beginWord);
        int l = beginWord.length();
        HashMap<String, List<String>> children = new HashMap<>();
        boolean find = false;
        while(!p.isEmpty() && !find){
            for(String s:p)
                dict.remove(s);
            Set<String> q = new HashSet<>();
            for(String str:p){
                char[] word = str.toCharArray();
                for(int i = 0; i < l; ++i){
                    char ch = word[i];
                    for(int j = 'a'; j <= 'z'; ++j){
                        if(j == ch)
                            continue;
                        word[i] = (char)j;
                        String w = new String(word);
                        if(w.equals(endWord)){
                            find = true;
                            List<String> list = children.getOrDefault(str, new ArrayList<>());
                            list.add(w);
                            children.put(str, list);
                        }else{
                            if(dict.contains(w) && !find){
                                List<String> list = children.getOrDefault(str, new ArrayList<>());
                                list.add(w);
                                children.put(str, list);
                                q.add(w);
                            }
                        }
                    }
                    word[i] = ch;
                } 
            }
            p = q;
        }
        if(find){
            List<String> path = new ArrayList<>();
            path.add(beginWord);
            bfs(res, path, children, beginWord, endWord);
        }
        return res;
    }
    private void bfs(List<List<String>> res,
                    List<String> path,
                    HashMap<String, List<String>> children,
                    String beginWord, String endWord){
        if(beginWord.equals(endWord)){
            res.add(new ArrayList(path));
            return;
        }
        if(!children.containsKey(beginWord))
            return;
        List<String> list = children.get(beginWord);
        for(String word:list){
            path.add(word);
            bfs(res, path, children, word, endWord);
            path.remove(word);
        }
    }
}