题解 | #牛群最短移动序列# java
牛群最短移动序列
https://www.nowcoder.com/practice/6473462e05ac4665baec04caf628abdd
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param beginWord string字符串
* @param endWord string字符串
* @param wordList string字符串一维数组
* @return int整型
*/
public int ladderLength (String beginWord, String endWord, String[] wordList) {
// write code here
Set<String> dict = new HashSet<>(Arrays.asList(
wordList)); // 将wordList转换为set，用于快速查找
if (!dict.contains(endWord)) {
return 0; // endWord不在字典中，无法到达
}
Queue<String> q = new LinkedList<>();
q.offer(beginWord);
Set<String> visited = new HashSet<>(); // 记录已经访问过的节点
visited.add(beginWord);
int steps = 0;
while (!q.isEmpty()) {
int size = q.size();
steps++;
for (int i = 0; i < size; i++) {
String curr = q.poll();
// 将当前节点的每个字母逐个替换为'a'~'z'，并查找是否有这个新的编号
char[] currChars = curr.toCharArray();
for (int j = 0; j < curr.length(); j++) {
char origChar = currChars[j];
for (char c = 'a'; c <= 'z'; c++) {
if (c == origChar) {
continue;
}
currChars[j] = c;
String transformed = new String(currChars);
if (transformed.equals(endWord)) {
return steps + 1; // 找到了endWord，返回路径长度
}
if (dict.contains(transformed) && !visited.contains(transformed)) {
q.offer(transformed);
visited.add(transformed);
}
}
currChars[j] = origChar; // 恢复原始状态
}
}
}
return 0; // 没有找到最短路径
}
}
使用的是Java编程语言。
该题考察的是使用广度优先搜索（BFS）解决图的最短路径问题。给定一个起始单词和一个目标单词，以及一个单词列表，我们需要找到从起始单词到目标单词的最短路径长度。
代码的文字解释如下：
- 将
wordList转换为HashSet，用于快速查找单词。 - 如果目标单词不在单词列表中，返回0，表示无法到达。
- 创建一个队列
q，并将起始单词加入队列。 - 创建一个集合
visited，用于记录已经访问过的单词，并将起始单词加入集合。 - 初始化步数
steps为0。 - 进入循环，直到队列为空。
- 在每次循环开始时，获取当前队列的大小，用于控制内层循环的迭代次数。
- 增加步数
steps。 - 在内层循环中，依次取出队列中的单词。
- 使用双重循环，将当前单词的每个字母逐个替换为'a'~'z'，生成新的转换后的单词。
- 如果转换后的单词等于目标单词，返回步数
steps + 1，表示找到了最短路径长度。 - 如果转换后的单词在单词列表中并且没有被访问过，将其加入队列和访问集合。
- 恢复当前单词到原始状态，并继续下一次循环。
- 如果循环结束后都没有找到最短路径，则返回0，表示无法到达目标单词。
