126. Word Ladder II

跟127. WordLadder其实是差不多的原理：

• 首先BFS一次，建立一颗以beginWord为root的树。但这棵树其实是不完整的，深度只到发现endWord位置。
• 再DFS一次，查找出所有具体的解。

其实还有很多可以优化的地方，比如如果BFS没找到解，其实可以省略DFS。

代码：

public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new ArrayList<List<String>>();
        Set<String> allWords = new HashSet<String>();

        // 如果endWord在词典中不存在，可以直接返回0
        boolean endWordExist = false;
        for (String word : wordList) {
            if (endWord.equals(word))
                endWordExist = true;
            if (!beginWord.equals(word))
                allWords.add(word);
        }

        // bad case
        if (!endWordExist)
            return result;

        // 每一层最多可能有26个节点，小写字母的a-z
        Set<String> nextWords = new HashSet<String>();
        Set<String> existWords = new HashSet<String>();
        Map<String, Set<String>> tree = new HashMap<String, Set<String>>(); // 用一个map去表示树的结构
        Deque<String> queue = new LinkedList<String>(); // 暂存路径
        nextWords.add(beginWord);
        queue.add(beginWord);

        // 先一次bfs构建出树的结构，再一次dfs找到所有解
        bfs2(nextWords, tree, existWords, allWords, endWord);
        dfs(tree, endWord, result, queue);

        return result;
    }

    private void bfs2(Set<String> nextWords, Map<String, Set<String>> tree, Set<String> existWords, Set<String> allWords, String endWord) {
        if (nextWords.size() == 0)
            return;

        // 这一层总共有哪些节点？
        Set<String> allChildren = new HashSet<String>();
        // 是否要在这一层停止迭代？
        boolean flag = false;

        for (String next : nextWords) {
            // next这个词下面，可能有哪些词？
            Set<String> children = new HashSet<String>();
            char[] charArray = next.toCharArray();
            // 暴力穷举所有可能的词
            for (int i = 0; i < charArray.length; i++) {
                for (char c = 'a'; c <= 'z'; c++) {
                    // 每次替换一个字母，最多也就26个子节点
                    char old = charArray[i];
                    charArray[i] = c;
                    String tmp = new String(charArray);
                    charArray[i] = old;

                    if (tmp.equals(endWord))
                        flag = true;

                    if (allWords.contains(tmp) && !existWords.contains(tmp))
                        children.add(tmp);
                }
            }
            allChildren.addAll(children);
            tree.put(next, children);
        }

        existWords.addAll(allChildren);

        // 在当前层就找到了endWord，停止迭代
        if (flag)
            return;
        else
            bfs2(allChildren, tree, existWords, allWords, endWord);
    }

    private void dfs(Map<String, Set<String>> tree, String endWord, List<List<String>> result, Deque<String> queue) {
        String current = queue.peekLast();
        // 找到了叶子节点
        if (!tree.containsKey(current)) {
            if (current.equals(endWord)) {
                List<String> list = new ArrayList<String>();
                list.addAll(queue);
                result.add(list);
            }
            return;
        }

        for (String child : tree.get(current)) {
            queue.addLast(child);
            dfs(tree, endWord, result, queue);
            queue.removeLast();
        }
    }
}