跳到主要内容

LeetCode 127. 单词接龙

本节目标

把单词转换建模为无权状态图，用 BFS 求最短序列长度。

这道题把搜索与剪枝综合中的“状态图最短路”落到单词转换：每次只能改一个字符，中间单词必须来自字典，求从起点到终点的最短序列长度。

查看 LeetCode 原题

题意与约束​

给定 beginWord、endWord 和单词表。一次转换只能改变一个位置，并且转换后的单词必须在单词表中。返回包含起点和终点在内的最短序列长度；无法到达时返回 0。

例如 hit → hot → dot → dog → cog 含 5 个单词，因此答案是 5，而不是 4。

朴素思路与瓶颈​

可以从起点枚举所有转换序列，但一个长度为 L 的单词，每层最多尝试 26L 次替换。若沿一条路走到底才回头，既可能先找到较长路径，也会反复进入同一个单词，搜索树迅速膨胀。

问题只关心最少转换次数，而且每次转换的代价相同。这正是无权图最短路，不需要枚举全部路径。

从单词表到状态图​

把每个合法单词看作节点；若两个单词只差一个字符，就在它们之间连边。显式比较每对单词需要大量工作，我们可以在 BFS 扩展当前单词时，逐位替换为 a 到 z，只保留仍在集合中的候选词。

BFS 按距离递增访问状态。队列初始放入 (beginWord, 1)；从距离为 d 的单词生成终点时，答案就是 d + 1。

访问标记必须在入队时完成。本题直接从未访问集合中删除候选词：一旦入队，后续路径就不能再次把它加入队列。这样既保证首次到达是最短距离，也避免同一层重复扩展。

开始前先检查 endWord 是否在单词表中。题目要求所有转换后的单词都合法；若终点不在表中，答案必为 0。

代码实现​

C++ 与 Python 都用集合同时承担“合法字典”和“尚未访问”两种职责。核心函数只处理已经准备好的字符串与单词表，不读取输入流。

C++17
#include <queue>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
    int ladderLength(
        string beginWord,
        string endWord,
        vector<string>& wordList
    ) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) {
            return 0;
        }

        queue<pair<string, int>> queue;
        queue.push({beginWord, 1});
        wordSet.erase(beginWord);

        while (!queue.empty()) {
            auto [word, distance] = queue.front();
            queue.pop();

            for (int index = 0; index < static_cast<int>(word.size()); index++) {
                const char original = word[index];
                for (char letter = 'a'; letter <= 'z'; letter++) {
                    if (letter == original) {
                        continue;
                    }
                    word[index] = letter;
                    if (word == endWord) {
                        return distance + 1;
                    }
                    if (wordSet.erase(word)) {
                        queue.push({word, distance + 1});
                    }
                }
                word[index] = original;
            }
        }

        return 0;
    }
};

复杂度分析​

设单词表有 N 个长度为 L 的单词。

  • 每个单词最多入队一次，每次尝试 26L 个候选；考虑构造或哈希字符串的 O(L) 成本，时间复杂度保守记为 O(26NL²)。
  • 集合与队列最多保存 O(N) 个单词，字符串总空间复杂度为 O(NL)。

易错点​

  • 把转换次数当成序列长度，返回少 1 的结果。
  • 没有先检查终点是否在字典中。
  • 出队时才删除访问标记，使同一个候选被多个父状态重复入队。
  • 替换一个位置后没有恢复原字符，影响下一个位置的枚举。
  • 使用 DFS 找到第一条路径就返回，误以为它一定最短。

模式迁移​

凡是“状态之间每次操作代价相同，求最少操作次数”的问题，都应先尝试建成无权图并使用 BFS。钥匙与门、密码锁、基因变化等题目只是状态表示和邻居生成方式不同；如果状态空间仍然过大，再考虑双向搜索等进阶方法。