Word Ladder

127. 单词接龙

分析

构建字典集合
- 将 wordList 存入哈希集合 S 中，方便快速判断单词是否存在
BFS 初始化
- 用 queue 队列维护当前单词，初始化队列并记录 beginWord 的距离为 0
- 用哈希表 dist 记录每个单词到 beginWord 的最短路径长度
BFS 遍历
- 每次从队列中取出当前单词 cur，尝试修改它的每一位字符
- 对每个字符位置，从 ‘a’ 到 ‘z’ 枚举替换，形成新单词 temp
  - 如果 temp 在字典中且未被访问过：
    - 更新 dist[temp] = dist[cur] + 1，并将其加入队列
    - 如果 temp 等于 endWord，返回转换次数 dist[temp] + 1
终止条件
- 如果 BFS 遍历结束仍未找到 endWord，返回 0

时间复杂度

总时间复杂度 O(L * 26 * N)，L 是单词长度，26 是字母表大小，N 是字典中单词数量

空间复杂度

空间复杂度为 O(N)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


class Solution
{
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList)
    {
        // 存储字典单词集合
        std::unordered_set<std::string> S;
        for (std::string word : wordList)
            S.insert(word);

        // 记录单词到起点的最短路径长度
        std::unordered_map<std::string, int> dist;
        dist[beginWord] = 0;

        std::queue<std::string> q;
        q.push(beginWord);

        while (!q.empty())
        {
            std::string cur = q.front();
            q.pop();

            // 枚举每个字符位置进行替换
            for (int i = 0; i < cur.size(); ++i)
            {
                std::string temp = cur;
                for (char j = 'a'; j <= 'z'; ++j)
                {
                    temp[i] = j; // 修改第 i 位字符
                    if (S.count(temp) && !dist.count(temp))
                    {
                        dist[temp] = dist[cur] + 1;
                        if (temp == endWord)
                            return dist[temp] + 1; // 返回结果
                        q.push(temp);
                    }
                }
            }
        }
        return 0; // 无法转换
    }
};