LeetCode.126.Word Ladder II 单词接龙 II

题目描述

126. Word Ladder II 给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
127. 每次转换只能改变一个字母。
128. 转换过程中的中间单词必须是字典中的单词。

说明:

• 如果不存在这样的转换序列，返回一个空列表。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

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

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

示例 2:

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

输出: []

解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

---

解题过程

BFS 广度优先搜索

这道题本质上是在图结构上的搜索问题，从 beginWord 开始，每次搜索能通过转换到达的单词（图的结点），依次搜索下去直到到达 endWord
由于是求从 beginWord 到 endWord 的最短路径，我们使用 BFS 广度优先搜索，一旦搜索到达 endWord 所在的层，就停止。

需要注意的点
1、必须提前构造好图结构存储下来，虽然也可以在 BFS 遍历过程中查找每个结点的邻接点list，但复杂度较高，无法通过。
2、必须用 visited 集合标记已访问过的结点，否则会有死循环
3、搜索到达 endWord 所在的层后，要遍历完当前层找到所有最短路径，因为从 beginWord 到 endWord 可能有多条最短路径，题目要求找到所有最短路径，而不是找到一个就行。
4、题目要求的是从 beginWord 到 endWord 的序列，所以我们需要保存每个结点的父节点序列，也就是 Queue 中存储的是 List，每个 List 的最后一个节点是当前要遍历的结点。

构造图存储结构时间复杂度为 O(n^2 * c)，其中 n 是字典长度，c 是字典中每个单词的长度，因为需要两次循环 O(n^2)，对比两个单词是否可转换复杂度为 O(c)。BFS 遍历图时间复杂度为 O(n^2)。所以总的时间复杂度为 O(n^2 * c)
空间复杂度 O(n^2)

private static class SolutionV202006 {
    Map<String, Set<String>> graph;
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        // wordList 中不包含 endWord 直接返回空
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return Collections.emptyList();
        }

        // 初始化图存储结构，邻接点 map, str -> Set 表示 str 的邻接点是 Set 中的元素（可以这样存的前提是图中无重复结点）
        graph = new HashMap<>();
        initGraph(wordList, beginWord);

        // 标识已访问过的结点
        Set<String> visited = new HashSet<>();

        // 结果集
        List<List<String>> res = new ArrayList<>();

        // queue 中存储的是每个结点及其父节点序列，从前往后存储，getLast() 是当前节点
        Queue<LinkedList<String>> queue = new LinkedList<>();
        queue.offer(new LinkedList<>(Arrays.asList(beginWord)));
        // BFS 层次遍历
        while (!queue.isEmpty()) {
            boolean find = false; // 当前层是否找到 endWord，找到则停止BFS
            int levelSize = queue.size(); // 当前层结点数
            for (int i = 0; i < levelSize; i++) {
                LinkedList<String> strList = queue.poll();
                visited.add(strList.getLast()); // 标记为已访问过
                // 找当前节点 strList.getLast() 能转换成的结点集合
                Set<String> convertSet = graph.get(strList.getLast());
                if (convertSet.contains(endWord)) {
                    // 当前层已到达 endWord
                    find = true;
                    strList.add(endWord);
                    res.add(strList);
                }
                // 从可转换集合中排除已遍历过的结点，并依次和父节点 list 拼接后加入 queue
                convertSet.stream().filter(str -> !visited.contains(str)).forEach(str -> {
                    LinkedList<String> newList = new LinkedList<>(strList);
                    newList.add(str);
                    queue.add(newList);
                });
            }
            if (find) {
                // 当前层已到达 endWord，结束 BFS
                break;
            }
        }
        return res;
    }

    // 初始化图存储结构，邻接点 map, str -> Set 表示 str 的邻接点是 Set 中的元素（可以这样存的前提是图中无重复结点）
    private void initGraph(List<String> wordList, String beginWord) {
        graph.put(beginWord, findConvertSet(wordList, beginWord));
        wordList.forEach(str -> graph.put(str, findConvertSet(wordList, str)));
    }

    // 返回 wordList 中可以被 target 转换成的字符串集合
    private Set<String> findConvertSet(List<String> wordList, String target) {
        return wordList.stream().filter(str -> convertable(target, str)).collect(Collectors.toSet());
    }

    // str1 改变一个字符可以转换为 str2 时返回 true
    private boolean convertable(String str1, String str2) {
        int diffCount = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                diffCount++;
            }
            if (diffCount > 1) {
                return false;
            }
        }
        return true;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_126_WordLadder2.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_126_WordLadder2.java

---