单词接龙小窍门大全473BFS解单词接龙
发布时间：2025年10月28日 点击：[0]人次
想了解更多数据结构以及算法题，可以关注微信公众号“数据结构和算法”，每天一题为你精彩解答。
问题描述
给定两个单词（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为例画个图来看下
代码如下，有详细的注释，应该不是很难理解
public int ladderLength(String beginWord, String endWord, List<String> wordList) { //把字典中的单词放入到set中，主要是为了方便查询 Set<String> dictSet = new HashSet<>(wordList); //创建一个新的单词，记录单词是否被访问过，如果没被访问过就加入进来 Set<String> visit = new HashSet<>(); //BFS中常见的队列，我们可以把它想象成为一颗二叉树，记录每一层的节点。 //或者把它想象成为一个图，记录挨着的节点，也就是每一圈的节点。这里我们把它想象成为一个图 Queue<String> queue = new LinkedList<>(); queue.add(beginWord); //这里的图是一圈一圈往外扩散的，这里的minlen可以看做扩散了多少圈， //也就是最短的转换序列长度 int minlen = 1; while (!queue.isEmpty()) { //这里找出每个节点周围的节点数量，然后都遍历他们 int levelCount = queue.size(); for (int i = 0; i < levelCount; i++) { //出队 String word = queue.poll(); //这里遍历每一个节点的单词，然后修改其中一个字符，让他成为一个新的单词， //并查看这个新的单词在字典中是否存在，如果存在并且没有被访问过，就加入到队列中 for (int j = 0; j < word.length(); j++) { char[] ch = word.toCharArray(); for (char c = 'a'; c <= 'z'; c++) { if (c == word.charAt(j)) continue; ch[j] = c; //修改其中的一个字符，然后重新构建一个新的单词 String newWord = String.valueOf(ch); //查看字典中有没有这个单词，如果有并且没有被访问过，就加入到队列中 //（Set的add方法表示把单词加入到队列中，如果set中没有这个单词 //就会添加成功，返回true。如果有这个单词，就会添加失败，返回false） if (dictSet.contains(newWord) && visit.add(newWord)) { //如果新单词是endWord就返回,这里访问的是第minlen圈的节点，然后 //新建的节点就是第minlen+1层 if (newWord.equals(endWord)) return minlen + 1; queue.add(newWord); } } } } //每往外扩一圈，长度就加1 minlen++; } return 0;}
2，从两边往中间开始计算
上面是从start开始往外扩散，这里还可以一个从start，一个从end开始往中间走，哪个圈的元素少就先遍历哪个，这样可以减少循环的次数，如果能相遇就返回
private int find(int minlen, Queue<String> startQueue, Queue<String> endQueue, Set<String> dictSet, Set<String> visit) { int startCount = startQueue.size(); int endCount = endQueue.size(); boolean start = startCount <= endCount; int count = start ? startCount : endCount; //哪个量少，遍历哪个 for (int i = 0; i < count; i++) { //出队 String word; if (start) word = startQueue.poll(); else word = endQueue.poll(); //这里遍历每一个节点的单词，然后修改其中一个字符，让他成为一个新的单词， //并查看这个新的单词在字典中是否存在，如果存在并且没有被访问过，就加入到队列中 for (int j = 0; j < word.length(); j++) { char[] ch = word.toCharArray(); for (char c = 'a'; c <= 'z'; c++) { if (c == word.charAt(j)) continue; ch[j] = c; //修改其中的一个字符，然后重新构建一个新的单词 String newWord = String.valueOf(ch); if (dictSet.contains(newWord)) { if (start) {//从前往后 if (endQueue.contains(newWord)) return minlen + 1; if (visit.add(newWord)) startQueue.add(newWord); } else {//从后往前 if (startQueue.contains(newWord)) return minlen + 1; if (visit.add(newWord)) endQueue.add(newWord); } } } } } //如果没有相遇就返回-1 return -1;}
总结
这道题上两种方式都能解决，第2种方式比第一种稍微要复杂一些，但运行效率要比第1种高。