- 正确答案：LeetCode 127 单词接龙（Word Ladder）是一道经典的图论 + BFS 问题。给定起始单词 beginWord、目标单词 endWord 和一个单词列表 wordList，每次只能改变一个字母，且变换后的单词必须在 wordList 中，求从 beginWord 到 endWord 的最短转换序列长度（含首尾），若无法转换则返回 0。标准解法是将每个单词视为图中的一个节点，两个单词之间有边当且仅当它们恰好相差一个字母（即“可转换”）。问题转化为无权无向图中两点间的最短路径长度，BFS 是最优解法，时间复杂度可控，且天然保证首次到达 endWord 时路径最短。示例输入： beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"] 输出：5（路径：hit → hot → dot → dog → cog） - 解答思路： 1. 预处理：将 wordList 转为哈希集合（unordered_set），便于 O(1) 查找； 2. 边界检查：若 endWord 不在 wordList 中，直接返回 0； 3. 初始化 BFS 队列（queue）和访问标记（unordered_set visited），将 beginWord 入队，step = 1； 4. BFS 主循环：对当前层所有单词，枚举其每一位（0~len-1），尝试替换为 'a'~'z'（跳过原字符），生成新单词； 5. 若新单词 == endWord，立即返回 step + 1； 6. 若新单词在 wordSet 中且未访问过，则入队并标记 visited； 7. 每层遍历完后 step++； 8. 队列空仍未找到，返回 0。关键优化点： - 使用「双向 BFS」可将时间复杂度从 O(M²×N) 降至 O(M×N×√L)，其中 M=单词长度，N=wordList 大小，L=最短路径长度。但校招面试中单向 BFS 已足够，双向属于进阶加分项。 - 字母替换时避免构造全量字符串再查表；可对当前单词字符数组做原地修改 + set 查找，减少 string 构造开销。 - 实际工业代码中需注意：wordList 可能含重复词或 beginWord 自身，应先去重并排除 beginWord（因题目保证 beginWord 不在 wordList 中，但健壮性考虑仍建议 erase）。 - 深度知识讲解： ● 底层建模本质是「隐式图构建」：图的顶点集 V = {w | w ∈ wordList ∪ {beginWord}}，边集 E 由“编辑距离为1”定义。不显式建邻接表，而是在 BFS 过程中按需生成邻居——这是空间优化的核心思想（隐式图 vs 显式图），避免 O(N²) 建边开销。 ● 时间复杂度分析： - 单向 BFS：共最多 N 个节点入队；对每个单词，生成 M×25 个邻接词（M位 × 25个替代字母），每次 set 查找 O(1)，故总时间 O(M×25×N) = O(M×N)； - 空间复杂度：O(N) 存储 visited 和 queue，O(N) 存储 wordSet。 ● 为什么不用 DFS？ DFS 会穷举所有路径，无法保证首次到达 endWord 就是最短路；即使加剪枝（如限制深度），也无法规避指数级回溯。而 BFS 层序遍历天然具备“最早发现最短路”的数学保证（无权图中，路径长度 = 层数）。 ● 编辑距离为1 的判定原理：两个等长字符串 s1、s2 满足 editDistance(s1,s2)==1 ⇔ 它们在且仅在一个下标 i 上字符不同。无需调用完整编辑距离算法（Levenshtein），只需一次遍历计数差异位数，O(M) 即可判断。本题中我们反向构造：固定 s1，枚举所有 distance-1 的 s2，比对 s2 是否在集合中，更高效。 ● 字符编码细节：C++ 中 'a'+i 是安全的（ASCII 连续），但 Java/Python 中同样适用；注意不要用 char c = 'a' + rand()%26 —— 此处是确定性枚举，非随机。 ● 关于“只变一个字母”的严格性：题目要求每次变换必须是字典中存在的单词，且仅一个字母不同。这意味着像 "abc" → "axc" → "aec" 是合法的两步，但 "abc" → "aec"（跳过中间）不被允许，因为这不是单次变换（差两位）。 ● 扩展考点（面试官可能追问）： - 如何输出具体路径（不止长度）？→ 在 queue 中存 pair> 或用 parent map 回溯； - 如果允许改变任意位置（包括插入/删除）？→ 变成编辑距离 ≤1 的图，邻接生成逻辑变为：删1、插1、换1，共 3×M 种操作； - 若 wordList 极大（1e6），如何加速？→ 启用双向 BFS；或预处理所有单词的「通配符模式」（如 "hot" → {"*ot","h*t","ho*"}），用哈希表建立 pattern→words 映射，将邻接生成从 O(M×25) 降为 O(M)，详见官方题解优化版； - C++ 中 unordered_set 的哈希冲突如何影响性能？→ 默认 string 哈希函数质量高，冲突率低；极端情况下可自定义哈希（但通常不必）。 - 代码示例（C++，带详细注释，生产级写法）： #include #include #include #include #include int ladderLength(std::string beginWord, std::string endWord, std::vector& wordList) { // 1. 构建快速查找集合，并检查 endWord 是否存在 std::unordered_set wordSet(wordList.begin(), wordList.end()); if (wordSet.find(endWord) == wordSet.end()) return 0; // 2. BFS 初始化 std::queue q; std::unordered_set visited; q.push(beginWord); visited.insert(beginWord); int steps = 1; // 3. BFS 主循环 while (!q.empty()) { int levelSize = q.size(); // 当前层节点数，用于分层计步 for (int i = 0; i < levelSize; ++i) { std::string curr = q.front(); q.pop(); // 4. 枚举每一位，尝试替换为 a-z for (int j = 0; j < curr.length(); ++j) { char original = curr[j]; // 保存原字符 for (char c = 'a'; c <= 'z'; ++c) { if (c == original) continue; // 跳过相同字符，避免无效自环 curr[j] = c; // 5. 检查新单词是否为目标 if (curr == endWord) return steps + 1; // 6. 检查是否合法且未访问 if (wordSet.count(curr) && visited.find(curr) == visited.end()) { visited.insert(curr); q.push(curr); } } curr[j] = original; // 恢复原字符，为下一位枚举准备 } } steps++; // 当前层全部扩展完毕，进入下一层 } return 0; // 无法到达 } 补充说明（面试表达技巧）： - 在白板/远程面试中，建议先口头阐述思路：“我将单词看作图节点，BFS 求最短路径。关键在于如何高效生成邻居——不是两两比较，而是对每个单词逐位替换25个字母，再查字典。这样避免 O(N²) 建边。” - 若被问“为什么不用 DFS”，回答：“DFS 无法保证首次到达即最短，需遍历所有路径并维护最小值，时间不可控；而 BFS 层序特性天然适配最短路径问题。” - 若被问“空间占用大怎么办”，可提：“可用双向 BFS，从 beginWord 和 endWord 同时出发，当两个访问集合出现交集时终止，空间和时间均减半。” 该题完整覆盖：图建模能力、BFS 应用场景理解、隐式图优化思想、字符串操作细节、边界处理意识——是校招中检验算法基本功的黄金题目。

字节业务中台一面

全站热榜

创作者周榜