当前位置：首页 > news >正文

力扣127.单词接龙讲解

news 2025/8/9 18:56:30

距离上一次刷题已经过去了.........嗯............我数一一下............整整十天，今天再来解一道算法题

由于这段时间准备简历，没咋写博客。。今天回来了！！！！！！！！！！！！！！！！

话不多说，看题：

题目:

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

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord

给你两个单词 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 中的所有字符串 互不相同

嘶。。。。太难了，不会。。。。

猝！！！！！

正片开始：

解题思路：

这道题可以使用广度优先搜索（BFS）算法来解决。BFS 算法从 beginWord 开始，逐层向外扩展，直到找到 endWord。以下是如何使用 BFS 算法解决这道题的思路：

使用队列 queue 来存储待访问的单词。
使用集合 visited 来记录已访问过的单词，避免重复访问。
初始化层数 level 为 1。
将 beginWord 加入队列 queue，并将 beginWord 加入集合 visited。
循环执行以下步骤，直到队列 queue 为空：
- 将队列 queue 中的所有单词出队。
- 对于每个出队的单词 currentWord：
  - 如果 currentWord 等于 endWord，则找到最短转换序列，返回层数 level。
  - 否则，获取 currentWord 的所有相邻单词 neighbors。
  - 对于每个相邻单词 neighbor：
    - 如果 neighbor 未被访问过，则将其加入队列 queue 和集合 visited。
- 将层数 level 加 1。
如果 BFS 结束后仍未找到 endWord，则返回 0。

具体代码实现：

import java.util.*;public class WordLadder {public int ladderLength(String beginWord, String endWord, List<String> wordList) {// 如果字典中不存在 endWord，则返回 0if (!wordList.contains(endWord)) {return 0;}// 使用队列进行广度优先搜索（BFS）Queue<String> queue = new LinkedList<>();queue.offer(beginWord);// 使用集合记录已访问过的单词，避免重复访问Set<String> visited = new HashSet<>();visited.add(beginWord);// 层数，从 1 开始int level = 1;while (!queue.isEmpty()) {int size = queue.size();// 当前层的单词全部出队for (int i = 0; i < size; i++) {String currentWord = queue.poll();// 如果当前单词等于 endWord，则找到最短转换序列，返回层数if (currentWord.equals(endWord)) {return level;}// 遍历当前单词的相邻单词List<String> neighbors = getNeighbors(currentWord, wordList);for (String neighbor : neighbors) {// 如果相邻单词未被访问过，则将其加入队列和 visited 集合if (!visited.contains(neighbor)) {queue.offer(neighbor);visited.add(neighbor);}}}// 层数加 1level++;}// 如果 BFS 结束后仍未找到 endWord，则返回 0return 0;}// 获取当前单词的相邻单词private List<String> getNeighbors(String word, List<String> wordList) {List<String> neighbors = new ArrayList<>();for (String candidate : wordList) {int diffCount = 0;// 比较两个单词，计算不同字符的数量for (int i = 0; i < word.length(); i++) {if (word.charAt(i) != candidate.charAt(i)) {diffCount++;}}// 如果不同字符的数量为 1，则 candidate 是相邻单词if (diffCount == 1) {neighbors.add(candidate);}}return neighbors;}
}