473，BFS解单词接龙

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

Dream is not about what you want, but what you do after knowing who you are.

理想不是想想而已，是看清自我后的不顾一切。

问题描述

给定两个单词（beginWord和endWord）和一个字典，找到从beginWord到endWord的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。

说明:

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

示例 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单词为中心点当做是第一圈，然后把字典中和beginWord只差一个字符的单词放到第二圈，然后再把和第二圈只差一个字符并且在字典中存在的单词放到第3圈……，一直这样放，放的时候要注意不能放之前放过的，并且在放的时候遇到endWord直接返回即可。

这里以示例1为例画个图来看下

代码如下，有详细的注释，应该不是很难理解

 1public int ladderLength(String beginWord, String endWord, List<String> wordList) {
 2    //把字典中的单词放入到set中，主要是为了方便查询
 3    Set<String> dictSet = new HashSet<>(wordList);
 4    //创建一个新的单词，记录单词是否被访问过，如果没被访问过就加入进来
 5    Set<String> visit = new HashSet<>();
 6    //BFS中常见的队列，我们可以把它想象成为一颗二叉树，记录每一层的节点。
 7    //或者把它想象成为一个图，记录挨着的节点，也就是每一圈的节点。这里我们把它想象成为一个图
 8    Queue<String> queue = new LinkedList<>();
 9    queue.add(beginWord);
10    //这里的图是一圈一圈往外扩散的，这里的minlen可以看做扩散了多少圈，
11    //也就是最短的转换序列长度
12    int minlen = 1;
13    while (!queue.isEmpty()) {
14        //这里找出每个节点周围的节点数量，然后都遍历他们
15        int levelCount = queue.size();
16        for (int i = 0; i < levelCount; i++) {
17            //出队
18            String word = queue.poll();
19            //这里遍历每一个节点的单词，然后修改其中一个字符，让他成为一个新的单词，
20            //并查看这个新的单词在字典中是否存在，如果存在并且没有被访问过，就加入到队列中
21            for (int j = 0; j < word.length(); j++) {
22                char[] ch = word.toCharArray();
23                for (char c = 'a'; c <= 'z'; c++) {
24                    if (c == word.charAt(j))
25                        continue;
26                    ch[j] = c;
27                    //修改其中的一个字符，然后重新构建一个新的单词
28                    String newWord = String.valueOf(ch);
29                    //查看字典中有没有这个单词，如果有并且没有被访问过，就加入到队列中
30                    //（Set的add方法表示把单词加入到队列中，如果set中没有这个单词
31                    //就会添加成功，返回true。如果有这个单词，就会添加失败，返回false）
32                    if (dictSet.contains(newWord) && visit.add(newWord)) {
33                        //如果新单词是endWord就返回,这里访问的是第minlen圈的节点，然后
34                        //新建的节点就是第minlen+1层
35                        if (newWord.equals(endWord))
36                            return minlen + 1;
37                        queue.add(newWord);
38                    }
39                }
40            }
41        }
42        //每往外扩一圈，长度就加1
43        minlen++;
44    }
45    return 0;
46}

2，从两边往中间开始计算

上面是从start开始往外扩散，这里还可以一个从start，一个从end开始往中间走，哪个圈的元素少就先遍历哪个，这样可以减少循环的次数，如果能相遇就返回

 1private int find(int minlen, Queue<String> startQueue, Queue<String> endQueue, Set<String> dictSet, Set<String> visit) {
 2    int startCount = startQueue.size();
 3    int endCount = endQueue.size();
 4    boolean start = startCount <= endCount;
 5    int count = start ? startCount : endCount;
 6    //哪个量少，遍历哪个
 7    for (int i = 0; i < count; i++) {
 8        //出队
 9        String word;
10        if (start)
11            word = startQueue.poll();
12        else
13            word = endQueue.poll();
14
15        //这里遍历每一个节点的单词，然后修改其中一个字符，让他成为一个新的单词，
16        //并查看这个新的单词在字典中是否存在，如果存在并且没有被访问过，就加入到队列中
17        for (int j = 0; j < word.length(); j++) {
18            char[] ch = word.toCharArray();
19            for (char c = 'a'; c <= 'z'; c++) {
20                if (c == word.charAt(j))
21                    continue;
22                ch[j] = c;
23                //修改其中的一个字符，然后重新构建一个新的单词
24                String newWord = String.valueOf(ch);
25                if (dictSet.contains(newWord)) {
26                    if (start) {//从前往后
27                        if (endQueue.contains(newWord))
28                            return minlen + 1;
29                        if (visit.add(newWord))
30                            startQueue.add(newWord);
31                    } else {//从后往前
32                        if (startQueue.contains(newWord))
33                            return minlen + 1;
34                        if (visit.add(newWord))
35                            endQueue.add(newWord);
36                    }
37                }
38            }
39        }
40    }
41    //如果没有相遇就返回-1
42    return -1;
43}