LeetCode 127. 单词接龙

Categories:

题目描述
思路分析
1. 解法一：BFS 最短路径（推荐）
相似题目

题目描述

✅ 127. 单词接龙

思路分析

解法一：BFS 最短路径（推荐）

核心思路：

将所有单词放入哈希集合，便于 O(1) 判断是否存在。

BFS 按层扩展，枚举当前单词每一位替换为 26 个字母的邻接单词。

首次到达 endWord 的层数即为最短转换长度。

复杂度分析：

时间复杂度：O(n _ L _ 26)，其中 n 为单词数量，L 为单词长度。

空间复杂度：O(n)，用于队列与哈希集合。

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return 0;
        }

        Deque<String> queue = new ArrayDeque<>();
        queue.offer(beginWord);
        int steps = 1;

        // BFS 按层扩展
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(endWord)) {
                    return steps;
                }

                // 枚举每个位置的替换字符
                char[] arr = cur.toCharArray();
                for (int p = 0; p < arr.length; p++) {
                    char old = arr[p];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == old) {
                            continue;
                        }
                        arr[p] = c;
                        String next = new String(arr);
                        if (dict.contains(next)) {
                            dict.remove(next);
                            queue.offer(next);
                        }
                    }
                    arr[p] = old;
                }
            }
            steps++;
        }

        return 0;
    }
}

func ladderLength(beginWord string, endWord string, wordList []string) int {
	dict := make(map[string]bool)
	for _, w := range wordList {
		dict[w] = true
	}
	if !dict[endWord] {
		return 0
	}

	queue := []string{beginWord}
	steps := 1

	// BFS 按层扩展
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			cur := queue[0]
			queue = queue[1:]
			if cur == endWord {
				return steps
			}

			// 枚举每个位置的替换字符
			arr := []byte(cur)
			for p := 0; p < len(arr); p++ {
				old := arr[p]
				for c := byte('a'); c <= byte('z'); c++ {
					if c == old {
						continue
					}
					arr[p] = c
					next := string(arr)
					if dict[next] {
						delete(dict, next)
						queue = append(queue, next)
					}
				}
				arr[p] = old
			}
		}
		steps++
	}

	return 0
}

相似题目

题目	难度	考察点
126. 单词接龙 II	困难	BFS/DFS
433. 最小基因变化	中等	BFS
752. 打开转盘锁	中等	BFS
200. 岛屿数量	中等	BFS/DFS
130. 被围绕的区域	中等	BFS/DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/35062296