0126. Word Ladder II ==================== 题目信息 -------- :题号: 0126. 单词接龙 II :难度: Hard :主题: 图、广度优先搜索、最短路径 DAG、回溯 :原题: `LeetCode 0126 `_ :重点: 用 BFS 确定最短层并保留同层多前驱,再沿最短路径 DAG 恢复全部序列 题目重述 -------- 给定起始单词 ``beginWord``、目标单词 ``endWord`` 和字典 ``wordList``,返回从起点变换到终点的所有最短 序列。相邻单词必须恰好有一个位置的字母不同,每次变换后的单词都必须属于字典;``beginWord`` 可以不在 字典中。每条答案都包含起点和终点,答案之间的顺序不限;若终点不在字典中或无法到达,返回空数组。 所有单词长度相同,只包含小写英文字母,字典内没有重复单词,且 ``beginWord != endWord``。 自建示例 -------- * ``beginWord = "red"``、``endWord = "tax"``、字典为 ``["ted", "tex", "tad", "tax", "rex"]``,三条最短序列是 ``red -> ted -> tad -> tax``、``red -> ted -> tex -> tax`` 和 ``red -> rex -> tex -> tax``; * ``beginWord = "hit"``、``endWord = "cog"``,若字典没有 ``cog``,返回空数组,即使存在通向其他 单词的变换; * 若 ``aaa -> aab -> abb`` 与 ``aaa -> aba -> abb`` 都合法,则 ``abb`` 必须同时保留 ``aab`` 和 ``aba`` 两个上一层来源,否则会漏掉一条最短序列。 C++ 实现 -------- .. code-block:: cpp #include #include #include #include #include #include class Solution { private: std::vector validNeighbors( const std::string& word, const std::unordered_set& dictionary ) { std::vector result; std::string candidate = word; for (int index = 0; index < static_cast(candidate.size()); ++index) { const char original = candidate[index]; for (char ch = 'a'; ch <= 'z'; ++ch) { if (ch == original) { continue; } candidate[index] = ch; if (dictionary.count(candidate)) { result.push_back(candidate); } } candidate[index] = original; } return result; } std::vector> queueCompletePaths( const std::string& beginWord, const std::string& endWord, const std::unordered_set& dictionary ) { std::queue> paths; paths.push({beginWord}); std::unordered_set unused = dictionary; unused.erase(beginWord); std::vector> answer; while (!paths.empty() && answer.empty()) { int levelSize = static_cast(paths.size()); std::unordered_set usedThisLevel; while (levelSize-- > 0) { std::vector path = std::move(paths.front()); paths.pop(); for (const std::string& next : validNeighbors(path.back(), unused)) { std::vector extended = path; extended.push_back(next); if (next == endWord) { answer.push_back(std::move(extended)); } else { paths.push(std::move(extended)); } usedThisLevel.insert(next); } } for (const std::string& word : usedThisLevel) { unused.erase(word); } } return answer; } void restorePaths( const std::string& word, const std::string& beginWord, const std::unordered_map>& parents, std::vector& reversedPath, std::vector>& answer ) { reversedPath.push_back(word); if (word == beginWord) { answer.emplace_back(reversedPath.rbegin(), reversedPath.rend()); } else { auto found = parents.find(word); if (found != parents.end()) { for (const std::string& parent : found->second) { restorePaths(parent, beginWord, parents, reversedPath, answer); } } } reversedPath.pop_back(); } std::vector> buildShortestPathDag( const std::string& beginWord, const std::string& endWord, const std::vector& wordList ) { std::unordered_set dictionary(wordList.begin(), wordList.end()); if (!dictionary.count(endWord)) { return {}; } std::unordered_map distance{{beginWord, 0}}; std::unordered_map> parents; std::queue queue; queue.push(beginWord); int targetDistance = -1; while (!queue.empty()) { const std::string word = queue.front(); queue.pop(); const int nextDistance = distance[word] + 1; if (targetDistance != -1 && nextDistance > targetDistance) { continue; } for (const std::string& next : validNeighbors(word, dictionary)) { auto found = distance.find(next); if (found == distance.end()) { distance[next] = nextDistance; parents[next].push_back(word); queue.push(next); if (next == endWord) { targetDistance = nextDistance; } } else if (found->second == nextDistance) { parents[next].push_back(word); } } } if (!distance.count(endWord)) { return {}; } std::vector> answer; std::vector reversedPath; restorePaths(endWord, beginWord, parents, reversedPath, answer); return answer; } public: std::vector> findLadders( std::string beginWord, std::string endWord, std::vector& wordList ) { return buildShortestPathDag(beginWord, endWord, wordList); } }; 题解 ---- 从单词序列还原成图问题 ~~~~~~~~~~~~~~~~~~~~~~ 把每个合法单词看成节点,恰好相差一个字母的两个单词之间连一条边。每次变换的代价都为一,于是题目不是 任意路径枚举,而是无权图中的“全部最短路径”。这两个限定缺一不可:DFS 能枚举路径,却可能先深入很长的 分支;普通 BFS 能得到最短距离,却若只给每个节点记录一个来源,又无法恢复全部答案。 邻居无需预先两两建图。对当前单词的每个位置尝试 ``a`` 到 ``z``,候选存在于哈希字典时,就得到一条真实 边。这样按需生成至多 ``25L`` 个不同候选,避免为字典中全部单词对做比较和保存完整邻接表。 方案一:BFS 队列直接保存完整路径 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 最接近原定义的方案把 ``[beginWord]`` 放入队列。BFS 每轮取出同样长度的路径,把每个合法邻居接到末尾; 首次出现终点的这一层就是最短层,但必须处理完整层,才能收齐其他同长度答案。 ``queueCompletePaths`` 还揭示了一个容易写错的细节:本层发现的单词不能立刻从 ``unused`` 删除。假设 ``aab`` 和 ``aba`` 位于同一层,它们都能到达 ``abb``;若第一条路径发现 ``abb`` 时就删除它,第二个 前驱对应的答案会消失。因此代码先放进 ``usedThisLevel``,完成整层后再统一删除。删除更早层访问过的单词 是安全的,因为重新到达它只会形成更长路径或环。 该方案正确且直接,但队列元素是路径而不是节点。大量候选共享同一前缀,代码仍要反复复制整条前缀;在 到达终点之前,许多最终不会成为答案的完整路径也会占用内存。瓶颈不在找邻居,而在过早展开并复制输出。 结构信息:最短路径只沿相邻层前进 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ BFS 首次发现节点时已经确定其最短距离。任何最短序列上的边都必须从距离 ``d`` 的节点走到距离 ``d+1`` 的节点;若走向同层或更浅层,已经消耗一条边却没有增加到起点的最短距离,整条序列不可能仍然最短。 因此搜索阶段只需为每个节点保存:它的最短距离,以及所有能以相同最短距离到达它的上一层节点。共享前缀 不再复制为多份路径,而被压缩为一张“最短路径 DAG”;真正的组合展开推迟到确定能到达终点之后。 为何第一次发现后仍要接纳同层前驱 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 处理从 ``word`` 到 ``next`` 的边时,令候选距离为 ``distance[word] + 1``: * ``next`` 从未发现:候选距离就是其最短距离,记录 ``word`` 并让 ``next`` 入队一次; * ``next`` 已经以同一候选距离发现:不再重复入队,但追加 ``word``,因为它代表另一条最短路径; * ``next`` 的已知距离更小:这条边会生成更长路线,不记录。 “节点只入队一次”压缩了搜索工作,“同距离前驱全部保留”保存了答案分叉,两者并不冲突。 终点出现后的停止边界 ~~~~~~~~~~~~~~~~~~~~ 首次发现 ``endWord`` 时得到 ``targetDistance``,但不能立即终止:队列中其他距离 ``targetDistance - 1`` 的节点仍可能直接连到终点,或者补充其他最短层节点的前驱。代码继续处理所有 ``nextDistance <= targetDistance`` 的节点,只停止生成更深一层。这样收齐最短 DAG,又不探索不可能属于 答案的更长后缀。 具体走读 ~~~~~~~~ 对示例 ``red -> tax``,BFS 保留的核心状态为: .. list-table:: :header-rows: 1 * - 距离 - 新发现节点 - 记录的前驱 * - 0 - ``red`` - 无 * - 1 - ``ted``、``rex`` - ``ted <- red``、``rex <- red`` * - 2 - ``tad``、``tex`` - ``tad <- ted``、``tex <- ted, rex`` * - 3 - ``tax`` - ``tax <- tad, tex`` ``tex`` 第一次由 ``ted`` 发现后已经入队;随后 ``rex`` 以相同距离到达它,只追加第二个前驱。回溯从 ``tax`` 选择 ``tad`` 或 ``tex``,选择 ``tex`` 后又可选择 ``ted`` 或 ``rex``,恰好恢复三条序列。 回溯为何不重不漏 ~~~~~~~~~~~~~~~~ 每条记录边都让距离严格减一,所以沿 ``parents`` 反向移动不可能成环,最终只能到达起点。任一最短序列 在每一层都有一条对应前驱边,递归会枚举它,因此不漏;两次不同的前驱选择至少产生一个不同单词,因此不 重复。``reversedPath`` 维护“终点到当前节点”的选择,抵达起点时反向复制为正序答案,返回后弹出当前节点, 让兄弟分支复用同一缓冲区。 主解选择与复杂度 ~~~~~~~~~~~~~~~~ 公开入口采用 ``buildShortestPathDag``。相较完整路径 BFS,它增加了距离表和前驱表,却删除了搜索期间的 路径前缀复制;只有确实属于最短答案的 DAG 才会在回溯阶段展开。完整路径方案保留为直觉基线,适合展示 “整层延迟删除”的必要性,但不作为主解。 设字典大小为 ``N``、单词长度为 ``L``。每个被发现节点至多出队一次,每次尝试 ``O(26L)`` 个字符串, 构造和哈希字符串需要 ``O(L)``,搜索期望时间为 ``O(26NL^2)``。前驱 DAG 占用 ``O(N + E)`` 条记录; 回溯时间和答案空间必然与所有返回序列的字符总量成正比,无法由只依赖 ``N`` 的多项式上界替代。