一、知识点:
BFS、队列、HashSet
二、文字分析:
使用了一个队列来进行广度优先搜索。首先,将起始词加入队列,然后开始循环遍历队列。每次从队列中取出一个词,将其进行变换,产生所有可能的下一步词,并将这些下一步词加入队列。如果某个下一步词与目标词完全相同,表示找到了最短移动序列,返回当前级别+1。如果队列为空仍然没有找到目标词,说明无法转换到最终目标,返回0。
三、编程语言:
java
四、正确代码:
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) {
Set<String> wordSet = new HashSet<>(Arrays.asList(wordList));
if (!wordSet.contains(endWord)) {
return 0; // 结束词不在字典中,无法转换
}
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int level = 0; // 转换序列的级别
while (!queue.isEmpty()) {
int size = queue.size();
level++;
for (int i = 0; i < size; i++) {
String word = queue.poll();
char[] arr = word.toCharArray();
for (int j = 0; j < arr.length; j++) {
char originalChar = arr[j];
for (char ch = 'a'; ch <= 'z'; ch++) {
if (ch == originalChar) {
continue;
}
arr[j] = ch;
String newWord = new String(arr);
if (newWord.equals(endWord)) {
return level + 1; // 找到最终目标,返回级别+1
}
if (wordSet.contains(newWord)) {
queue.offer(newWord);
wordSet.remove(newWord); // 确保不会重复访问已经入队列的单词
}
}
arr[j] = originalChar; // 恢复原始字符
}
}
}
return 0; // 无法转换到最终目标
}
}

京公网安备 11010502036488号