单词接龙问题的广度优先搜索与路径还原算法实现
在算法面试中，单词接龙（Word Ladder）是一类经典的图论问题。该问题通常要求在给定的字典中，通过每次只改变一个字母的方式，寻找从起始单词到目标单词的最短转换路径。此类问题本质上是在一个隐含的图中寻找最短路径，因此广度优先搜索（BFS）是核心的解题思路。
寻找最短转换序列的长度
给定起始单词 beginWord、目标单词 endWord 和一个字典 wordList，我们需要计算从起点到终点的最短路径包含的单词数。如果无法到达，则返回 0。
解题思路
由于每一步转换的权值相等（均为 1），BFS 是寻找最短路径的最佳选择。为了提高搜索效率，我们可以将字典存入哈希表中，以便在 $O(1)$ 时间内判断转换后的单词是否存在。此外，通过分层遍历的方式，可以清晰地统计当前的转换步数。
代码实现
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
if (dict.find(endWord) == dict.end()) return 0;
queue<string> q;
q.push(beginWord);
int step = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
string curr = q.front();
q.pop();
if (curr == endWord) return step;
// 尝试修改当前单词的每一个位置
for (int j = 0; j < curr.size(); ++j) {
char originalChar = curr[j];
for (char c = 'a'; c <= 'z'; ++c) {
if (c == originalChar) continue;
curr[j] = c;
if (dict.count(curr)) {
q.push(curr);
dict.erase(curr); // 避免重复访问
}
}
curr[j] = originalChar;
}
}
step++;
}
return 0;
}
};
获取所有最短转换路径
在进阶版问题中，目标不再是长度，而是需要返回所有满足最短条件的转换路径序列。
解题思路
本题需要结合 BFS 和回溯算法（DFS）。
- BFS 阶段：构建一个邻接表来记录每个单词的"父节点"（即哪些单词可以经过一次变换到达当前单词）。为了保证是最短路径，我们需要记录每个单词被访问时的层级（distance），只有当新生成的单词处于当前层级的下一层时，才将其建立连接。
- DFS 阶段：从目标单词
endWord开始，利用 BFS 阶段构建的邻接表，反向回溯到beginWord，从而重构出所有路径。
代码实现
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
vector<vector<string>> results;
unordered_set<string> dict(wordList.begin(), wordList.end());
if (dict.find(endWord) == dict.end()) return results;
// 记录单词到起点的最短距离
unordered_map<string, int> distMap;
// 记录路径前驱节点
unordered_map<string, vector<string>> predecessors;
queue<string> q;
q.push(beginWord);
distMap[beginWord] = 0;
bool found = false;
int wordLen = beginWord.size();
while (!q.empty()) {
string u = q.front();
q.pop();
if (u == endWord) {
found = true;
continue;
}
string v = u;
for (int i = 0; i < wordLen; ++i) {
char oldChar = v[i];
for (char c = 'a'; c <= 'z'; ++c) {
v[i] = c;
if (dict.count(v)) {
if (distMap.find(v) == distMap.end()) {
distMap[v] = distMap[u] + 1;
predecessors[v].push_back(u);
q.push(v);
} else if (distMap[v] == distMap[u] + 1) {
predecessors[v].push_back(u);
}
}
}
v[i] = oldChar;
}
}
if (found) {
vector<string> path = {endWord};
backtrack(endWord, beginWord, predecessors, path, results);
}
return results;
}
private:
void backtrack(const string& current, const string& start,
unordered_map<string, vector<string>>& pre,
vector<string>& path, vector<vector<string>>& res) {
if (current == start) {
vector<string> validPath = path;
reverse(validPath.begin(), validPath.end());
res.push_back(validPath);
return;
}
for (const string& p : pre[current]) {
path.push_back(p);
backtrack(p, start, pre, path, res);
path.pop_back();
}
}
};
性能优化要点
- 双向 BFS：对于第一题，从起点和终点同时开启 BFS 可以显著减小搜索树的规模，在大数据量下性能提升明显。
- 状态压缩：在单词长度固定且字符集有限的情况下，可以将单词映射为整数或使用位运算进行比对，但在大多数工程实践和面试中，使用哈希表已足够高效。
- 空间换时间：第二题中构建前驱节点字典是为了避免在 DFS 阶段进行盲目搜索，确保回溯的每一条路径都是最短路径的一部分。
