LeetCode-127-单词接龙

127. 单词接龙

难度困难

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

• 序列中第一个单词是 beginWord 。
• 序列中最后一个单词是 endWord 。
• 每次转换只能改变一个字母。
• 转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

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

「转换」意即：两个单词对应位置只有一个字符不同，例如 "hit" 与 "hot"，这种转换是可以逆向的，因此，根据题目给出的单词列表，可以构建出一个无向（无权）图

image-20210611091944083

我们在遍历一开始，把所有的单词列表放进一个哈希表中，然后在遍历的时候构建图，每一次得到在单词列表里可以转换的单词，复杂度是O(26×wordLen)，借助哈希表，找到邻居与 NN 无关；

双向广度优先遍历

• 已知目标顶点的情况下，可以分别从起点和目标顶点（终点）执行广度优先遍历，直到遍历的部分有交集。这种方式搜索的单词数量会更小一些；
• 更合理的做法是，每次从单词数量小的集合开始扩散；
• 这里 beginVisited 和 endVisited 交替使用，等价于单向 BFS 里使用队列，每次扩散都要加到总的 visited 里。

image-20210611092731748

class Solution {
    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return 0;
        }
        HashSet<String> startSet = new HashSet<>();
        HashSet<String> endSet = new HashSet<>();
        HashSet<String> visit = new HashSet<>();
        startSet.add(beginWord);
        endSet.add(endWord);
        for (int len = 2; !startSet.isEmpty(); len++) {
            HashSet<String> nextSet = new HashSet<>();
            for (String w : startSet) {
                for (int j = 0; j < w.length(); j++) {
                    char[] ch = w.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {//把单词的每一位修改为a-z，看单词表中是否存在
                        if (c != w.charAt(j)) {
                            ch[j] = c;
                            String next = String.valueOf(ch);//每一位a-z变换过的单词
                            if (endSet.contains(next)) {
                                return len;//双端碰到了，返回结果
                            }
                            if (dict.contains(next) && !visit.contains(next)) {//字典中包含该单词，并且没有发散过的单词，加入集合
                                nextSet.add(next);
                                visit.add(next);//加入已经变化过的单词
                            }
                        }
                    }
                }
            }
            startSet = (nextSet.size() < endSet.size()) ? nextSet : endSet;//start end 那边集合元素少，从那边开始作为遍历转化
            endSet = (startSet == nextSet) ? endSet : nextSet;
        }
        return 0;
    }
}

image-20210611093509238