一、知识点:
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; // 无法转换到最终目标 } }