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

LeetCode 127：单词接龙

ds 2025/7/26 14:59:57

LeetCode 127：单词接龙

在这里插入图片描述

问题本质：最短转换序列的长度

给定两个单词 beginWord 和 endWord，以及字典 wordList，要求找到从 beginWord 到 endWord 的最短转换序列（每次转换仅改变一个字母，且中间单词必须在 wordList 中），返回序列的单词数；若无法转换，返回 0。

核心思路：广度优先搜索（BFS）

BFS 天然适合解决最短路径问题，因为它按层次遍历，第一次到达目标节点时的层数即为最短路径长度。

关键观察：

邻居生成：每个单词的“邻居”是改变一个字母后得到的所有可能单词（需在 wordList 中）。
去重处理：用集合记录已访问的单词，避免重复处理（否则会导致无限循环或超时）。

算法步骤详解

步骤 1：预处理与边界检查

将 wordList 转换为 HashSet，确保查找时间为 O(1)。
若 endWord 不在 wordList 中，直接返回 0（无法转换）。

步骤 2：初始化 BFS

队列：存储当前处理的单词及当前步数（通过分层遍历实现，队列中同一层的单词对应相同步数）。
访问集合：记录已处理的单词，避免重复入队。
初始状态：将 beginWord 入队，步数为 1（beginWord 是序列的第一个单词）。

步骤 3：分层遍历（BFS 核心）

遍历当前层：每次取出队列中当前层的所有单词（通过 queue.size() 获取层大小）。
生成邻居：对每个单词，遍历其每个字符位置，尝试替换为 a-z 中除原字符外的所有可能，生成新单词。
检查终止条件：若新单词是 endWord，直接返回 当前步数 + 1（新单词是下一层，步数加1）。
合法邻居入队：若新单词在 wordList 中且未被访问，标记为已访问并加入队列。

步骤 4：处理剩余情况

若遍历完所有可能仍未找到 endWord，返回 0。

完整代码（Java）

import java.util.*;class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {// 1. 预处理：转换为集合，加速查找Set<String> wordSet = new HashSet<>(wordList);// 边界检查：endWord 不在字典中，直接返回 0if (!wordSet.contains(endWord)) {return 0;}// 2. 初始化 BFS：队列（存储单词）、访问集合、步数Queue<String> queue = new LinkedList<>();Set<String> visited = new HashSet<>();queue.offer(beginWord);visited.add(beginWord);int step = 1; // beginWord 是第一个单词，步数初始为 1// 3. 分层遍历while (!queue.isEmpty()) {int currentLevelSize = queue.size(); // 当前层的单词数量for (int i = 0; i < currentLevelSize; i++) {String currentWord = queue.poll();// 生成所有可能的邻居（改变一个字母）for (int j = 0; j < currentWord.length(); j++) {// 尝试替换为 a-z 中除原字符外的所有字母for (char c = 'a'; c <= 'z'; c++) {if (c == currentWord.charAt(j)) {continue; // 跳过原字符，保证只改变一个字母}// 构造新单词StringBuilder sb = new StringBuilder(currentWord);sb.setCharAt(j, c);String newWord = sb.toString();// 终止条件：找到 endWord，返回步数+1if (newWord.equals(endWord)) {return step + 1;}// 合法邻居：在字典中且未被访问if (wordSet.contains(newWord) && !visited.contains(newWord)) {visited.add(newWord);queue.offer(newWord);}}}}step++; // 处理完当前层，步数加 1}// 4. 遍历结束仍未找到，返回 0return 0;}
}

关键细节解析

邻居生成优化：
对每个字符位置，遍历 26 个字母（跳过原字符），确保仅改变一个字母。时间复杂度为 O(L×26)（L 是单词长度，最多为 10），高效可控。
分层遍历的意义：
通过 queue.size() 分层处理，保证每次处理的是同一步数的单词，确保第一次到达 endWord 时的步数是最小值。
去重的必要性：
若不标记已访问，同一单词可能被多次入队，导致时间复杂度过高（例如，hot 可能被不同路径多次生成）。

复杂度分析

时间复杂度：O(N×L×26)，其中 N 是 wordList 的长度（最多 5000），L 是单词长度（最多 10）。每个单词生成 L×25 个邻居（排除原字符），整体可接受。
空间复杂度：O(N)，队列和访问集合最多存储 N 个单词。

示例验证

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
过程：hit → hot → dot → dog → cog，共 5 步。代码中，当处理 dog 时生成 cog，返回 step + 1 = 4 + 1 = 5，符合预期。

示例 2：