时间轴

2025-11-24

init

题目：

P127 单词接龙

https://leetcode.cn/problems/word-ladder/description/?envType=study-plan-v2&envId=top-interview-150

BFS暴力枚举，这是我最先想出的方法，但是效率很低。

BFS暴力枚举

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <string>
#include <queue>
#include <unordered_set>
#include <vector>

using std::string;
using std::unordered_set;
using std::vector;
using std::queue;

class Solution {
    private:
	bool is_neighbor(string word, string possible_neighbor)
	{
		int diff_cnt = 0, n = word.size();
		if (possible_neighbor.size() != n) {
			return false;
		}
		for (int i = 0; i < n; i++) {
			if (word[i] != possible_neighbor[i]) {
				diff_cnt++;
			}
			if (diff_cnt > 1) {
				return false;
			}
		}
		return true;
	}

    public:
	int ladderLength(string beginWord, string endWord, vector<string> &wordList)
	{
		int i, n, level = 1;
		queue<string> que;

		unordered_set<string> visited;
		string curr_word;

		que.push(beginWord);
		visited.insert(beginWord);

		while (!que.empty()) {
			n = que.size();

			for (i = 0; i < n; i++) {
				curr_word = que.front();
				que.pop();
				if (curr_word == endWord) {
					return level + 1;
				}
				for (auto &possible_neighbor : wordList) {
					if (!visited.count(possible_neighbor) &&
					    is_neighbor(curr_word, possible_neighbor)) {
						que.push(possible_neighbor);
						visited.insert(possible_neighbor);
					}
				}
			}
			level++;
		}
		return 0;
	}
};

BFS+虚拟节点优化建图

官方题解：我们先给每一个单词标号，即给每个单词分配一个 id。创建一个由单词 word 到 id 对应的映射 wordId，并将 beginWord 与 wordList 中所有的单词都加入这个映射中。之后我们检查 endWord 是否在该映射内，若不存在，则输入无解。我们可以使用哈希表实现上面的映射关系。

然后我们需要建图，依据朴素的思路，我们可以枚举每一对单词的组合，判断它们是否恰好相差一个字符，以判断这两个单词对应的节点是否能够相连。但是这样效率太低，我们可以优化建图。

具体地，我们可以创建虚拟节点。对于单词 hit，我们创建三个虚拟节点 it、ht、hi*，并让 hit 向这三个虚拟节点分别连一条边即可。如果一个单词能够转化为 hit，那么该单词必然会连接到这三个虚拟节点之一。对于每一个单词，我们枚举它连接到的虚拟节点，把该单词对应的 id 与这些虚拟节点对应的 id 相连即可。

最后我们将起点加入队列开始广度优先搜索，当搜索到终点时，我们就找到了最短路径的长度。注意因为添加了虚拟节点，所以我们得到的距离为实际最短路径长度的两倍。同时我们并未计算起点对答案的贡献，所以我们应当返回距离的一半再加一的结果。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    unordered_map<string, int> wordId;
    vector<vector<int>> edge;
    int nodeNum = 0;

    void addWord(string& word) {
        if (!wordId.count(word)) {
            wordId[word] = nodeNum++;
            edge.emplace_back();
        }
    }

    void addEdge(string& word) {
        addWord(word);
        int id1 = wordId[word];
        for (char& it : word) {
            char tmp = it;
            it = '*';
            addWord(word);
            int id2 = wordId[word];
            edge[id1].push_back(id2);
            edge[id2].push_back(id1);
            it = tmp;
        }
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        for (string& word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.count(endWord)) {
            return 0;
        }
        vector<int> dis(nodeNum, INT_MAX);
        int beginId = wordId[beginWord], endId = wordId[endWord];
        dis[beginId] = 0;

        queue<int> que;
        que.push(beginId);
        while (!que.empty()) {
            int x = que.front();
            que.pop();
            if (x == endId) {
                return dis[endId] / 2 + 1;
            }
            for (int& it : edge[x]) {
                if (dis[it] == INT_MAX) {
                    dis[it] = dis[x] + 1;
                    que.push(it);
                }
            }
        }
        return 0;
    }
};