leetcode127：单词接龙-EW帮帮网

字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同

步骤 1：分析问题

题目本质是一个最短路径搜索问题，其中图的节点是单词，边是单词间的转换条件（只差一个字母）。需要判断从 beginWord 到 endWord 是否存在路径，如果存在，求出路径长度。

输入输出条件

输入：
- beginWord：起始单词。
- endWord：目标单词。
- wordList：字典（可能包含 endWord，但不一定包含 beginWord）。
输出：
- 从 beginWord 到 endWord 的最短转换序列的单词数目；若不存在，返回 0。

限制条件

所有单词长度相等（beginWord.length == endWord.length == wordList[i].length）。
wordList 中的单词互不相同。

边界条件

endWord 不在 wordList 中：返回 0。
单词长度限制（1 <= 长度 <= 10）：限制了总的转换状态空间。
字典大小限制（最多 5000）：意味着可以构建图节点上限为 5001。

步骤 2：解题步骤和算法分析

最佳算法设计

采用**广度优先搜索（BFS）**来解决最短路径问题。这种算法适合无权图的最短路径搜索，特点是逐层扩展，找到目标时即为最短路径。

算法步骤

预处理：
- 用 unordered_set 存储 wordList，便于 O(1) 时间查找。
- 如果 endWord 不在字典中，直接返回 0。
构建邻接关系：
- 对每个单词，修改每个字符，用 'a' 到 'z' 的字母尝试替换，生成新单词。
- 若新单词存在于字典中，将其作为当前单词的邻接点。
BFS 寻找最短路径：
- 初始化队列，存入起点 beginWord 和步数 1。
- 每次从队列中取出一个单词，检查其邻接单词。
- 若某个邻接单词是 endWord，返回步数加 1。
- 将访问过的单词从字典中移除（避免重复访问）。
返回结果：
- 若 BFS 遍历完所有节点仍未找到路径，返回 0。

时间和空间复杂度分析

时间复杂度：
- 构造邻接关系需要 O(L × 26 × N)，其中 L 是单词长度，N 是字典大小。
- BFS 遍历每个单词一次，总共最多 O(N)。
- 综合复杂度：O(L × N)。
空间复杂度：
- 字典和队列共占用 O(N) 空间。

步骤 3：实现代码（C++）

class Solution {
public:
   // 广度优先搜索算法实现
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    // 如果目标单词不在字典中，直接返回 0
    if (dict.find(endWord) == dict.end()) return 0;

    // 初始化队列用于 BFS
    queue<pair<string, int>> q;
    q.push({beginWord, 1}); // 存入起始单词和步数

    // 开始 BFS
    while (!q.empty()) {
        auto [currentWord, steps] = q.front();
        q.pop();

        // 遍历当前单词的每个字符位置
        for (int i = 0; i < currentWord.size(); i++) {
            string tempWord = currentWord;
            for (char c = 'a'; c <= 'z'; c++) {
                tempWord[i] = c; // 替换字符
                // 如果是目标单词，返回步数 + 1
                if (tempWord == endWord) return steps + 1;

                // 如果新单词在字典中，加入队列并从字典中移除
                if (dict.find(tempWord) != dict.end()) {
                    q.push({tempWord, steps + 1});
                    dict.erase(tempWord);
                }
            }
        }
    }
    // 未找到路径
    return 0;
}
};

代码注释

unordered_set 用于快速查找是否某单词在字典中。
BFS 保证找到的路径是最短的。
每访问一个单词，将其从字典中移除，避免冗余计算。

步骤 4：问题的启发

广度优先搜索的应用：BFS 是解决无权图最短路径问题的利器。此题的状态空间较小，BFS 能高效处理。
状态压缩与剪枝：通过实时从字典中移除访问过的单词，大大降低了无效计算。
多源路径优化：可扩展到从多个起点同时寻找目标（如双向 BFS）。

步骤 5：实际应用

实际场景：拼写纠正系统

问题背景：在搜索引擎中，用户经常输入错误单词。通过最短路径算法，可以推荐更接近的正确单词。
实现方法：
1. 把所有可能的单词存储为图节点。
2. 对用户输入单词运行 BFS，找到最短路径的近似单词。
示例：
- 输入 hte，推荐 the（只需修改一个字符）。
- 应用场景：搜索引擎、输入法纠错等。

这种算法的思想还可以应用于 DNA 序列比对、社交网络最短距离分析等领域。

leetcode127：单词接龙