题目描述

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足：

• 每对相邻的单词之间仅有单个字母不同。
• 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
• sk == endWord

给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回。

示例 1：

输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出：[[“hit”,“hot”,“dot”,“dog”,“cog”],[“hit”,“hot”,“lot”,“log”,“cog”]]
解释：存在 2 种最短的转换序列：
“hit” -> “hot” -> “dot” -> “dog” -> “cog”
“hit” -> “hot” -> “lot” -> “log” -> “cog”

示例 2：

输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出：[]
解释：endWord “cog” 不在字典 wordList 中，所以不存在符合要求的转换序列。

提示：

• 1 <= beginWord.length <= 7
• endWord.length == beginWord.length
• 1 <= wordList.length <= 1000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有单词 互不相同

题目分析

该题目的简单类型在上篇文章 leetcode 127. 单词接龙 中进行了详细的分析，要看详细的分析请看上篇分析。那么这篇文章在上篇文章的基础上进行了修改，并添加了记录路径的方法。

解题方案：
（1）同样使用双向BFS的方法，每次从队列长度小的一端开始搜索。（2）在对某一层BFS开始之前，先将队列中的全部元素进行标记（至于为什么这么做，后边会解释）。（3）然后开始BFS，如果遍历到的节点未被标记，那么将该节点放入队列中，如果该节点存在于另一个队列中，说明已经找到最短的路径了。（4）此时将该层节点遍历结束后，方可进行回溯记录路径。（5）此外，需要在遍历节点的时候，通过判断这次遍历是从后向前还是从前向后，以确定构建的图的起始节点和结束节点。

（2）在对某一层BFS开始之前，先将队列中的全部元素进行标记。

假设遍历到了上图标记的位置，此时队列中的元素为 [ dot, lot] ，再次向后遍历的话，因为 dog 和 hot 都与 dot 相连，那么这两个元素都会入队列，可 hot 入队之后，程序的运行就会产生一个环形结构，这会对程序运行效率是极其不友好的，像这种情况，我们希望的是只将 dog 入队。因此，在程序开始之处，通过 wordList 构建一个wordListSet集合，集合中是全部未遍历过的元素。当队列中的元素是橘黄色指针指向的位置的时候，先将队列中的全部元素从wordListSet中删除（表示上一层的元素全部访问过），然后再遍历后边一层的元素（即：dog和log）后边一层中，只有存在于wordListSet中的元素才能入队。

（5）回溯建图

如上图所示，假设遍历到了箭头指向的位置（将hot从队列中弹出，并将[dot, lot]放入队列中），如果我们从正方向遍历的时候，map<key, val>中的 key 就是 hot , val 就是[dot, lot]，即 map<hot, [dot, lot]>

如上图所示，假设遍历到了箭头指向的位置（将log从队列中弹出并将lot放入队列中），如果从反方向遍历的时候，map<key, val>中的 key 就是 lot , val 就是 log，即 map<lot, log>。

代码

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

        wordList.add(beginWord);

        // 构建一个标记集合，开始的时候，每个word都在集合中。后边每次将元素放到队列中，便将该元素从集合中删除，以实现标记功能
        Set<String> wordListSet = new HashSet<>(wordList);

        if (!wordListSet.contains(endWord)) {
            return new ArrayList<>();
        }

        // 标记是不是已经找到了最短的路径，并用res来记录这些路径
        boolean found = false;
        List<List<String>> res = new ArrayList<>();

        // 构建map, 用来记录单词之间的关系；如上问题（5）
        Map<String, Set<String>> map = new HashMap<>(wordListSet.size());

        // 使用双向的BFS来检索最短的变换路径
        Queue<String> queueBegin = new ArrayDeque<>();
        Queue<String> queueEnd = new ArrayDeque<>();
        queueBegin.add(beginWord);
        queueEnd.add(endWord);

        // 每次只对比较短的BFS进行搜索，使用reverse标记两个方向的队列是不是交换过。
        boolean reverse = false;

        while (!queueBegin.isEmpty() && !queueEnd.isEmpty()) {

            // 只对比较短的队列进行广度优先搜索
            if (queueBegin.size() > queueEnd.size()) {
                Queue<String> queue = queueBegin;
                queueBegin = queueEnd;
                queueEnd = queue;

                // 标记是不是转换过，如果转换过的话，需要在构建图的时候将两个节点逆转
                reverse = !reverse;
            }

			// 将上一层访问过的节点从集合中删除
            wordListSet.removeAll(queueBegin);

			// queueBegin为当前遍历的队列，queueEnd是从另一端开始遍历的队列。
			// 根据queueEnd创建一个集合，用来判断遍历到的单词是不是出现在另一端遍历的队列中
            Set<String> queueEndToSet = new HashSet<>(queueEnd);

            int count = queueBegin.size();
            
            // 循环中为遍历BFS的当前层，并将下一层放到队列中去
            while (--count >= 0) {

                String key = queueBegin.remove();

                char[] keys = key.toCharArray();
                for (int i = 0; i < keys.length; i++) {
                    char c = keys[i];
                    for (char j = 'a'; j <= 'z'; j++) {
                        keys[i] = j;
                        String newStr = new String(keys);

                        // 如果当前元素存在于另一个队列中，说明找到了最短的路径，此时只需要将当前的两个对列遍历一遍，找到全部的结果集，而不需要再次向下遍历。
                        // 提高效率的方法，将queueEnd队列转化为一个Set，查找复杂度从O(n)转化成O(logn)
                        if (queueEndToSet.contains(newStr)) {
                            found = true;
                        }

                        // 如果未被访问过，那么将该元素放到queueBegin中。
                        if (wordListSet.contains(newStr)) {
                            queueBegin.add(newStr);
                        }

                        // 通过判断是不是reverse过，来构建节点关系图（保证其正向）
                        if (wordListSet.contains(newStr) || queueEndToSet.contains(newStr)) {
                            Set<String> subList;
                            if (reverse) {
                                subList = map.get(newStr);
                                if (subList == null) {
                                    subList = new HashSet<>();
                                }
                                subList.add(key);
                                map.put(newStr, subList);
                            } else {
                                subList = map.get(key);
                                if (subList == null) {
                                    subList = new HashSet<>();
                                }
                                subList.add(newStr);
                                map.put(key, subList);
                            }
                        }
                    }
                    keys[i] = c;
                }
            }

            // 将其放到最后进行遍历，原因在于：在构建图的时候，需要考虑到，此时两个遍历方向的队列已经到了中间层。如果得到结果就直接返回的话，肯定会导致缺少路径。
            // 因此在while(count--)之后再回溯记录路径，便会找到全部的路径
            if (found) {
                // 找到了该元素，调用回溯算法将返回结果集列表
                List<String> path = new ArrayList<>();
                path.add(beginWord);
                dfs(map, path, res, beginWord, endWord);
                return res;
            }

        }
        return res;
    }

	// 回溯法记录路径
    private void dfs(Map<String, Set<String>> map, List<String> path, List<List<String>> res, String beginWord, String endWord) {
        if (beginWord.equals(endWord)) {
            res.add(new ArrayList<>(path));
            return;
        }

        if (map.get(beginWord) != null) {
            for (String str: map.get(beginWord)) {
                path.add(str);
                dfs(map, path, res, str, endWord);
                path.remove(str);
            }
        }
    }

执行结果：