0127. Word Ladder ================= 题目信息 -------- :题号: 0127. 单词接龙 :难度: Hard :主题: 图、广度优先搜索、双向搜索、哈希集合 :原题: `LeetCode 0127 `_ :重点: 把单词变换建模为无权最短路,按需生成邻居,并用双向 BFS 缩小搜索前沿 题目重述 -------- 给定 ``beginWord``、``endWord`` 和字典 ``wordList``。每次必须恰好修改一个字母,修改后得到的单词必须 在字典中;起点本身可以不在字典中。返回最短变换序列包含的单词数量,起点和终点都计数;无法到达时返回 ``0``。 所有单词长度相同,只包含小写英文字母,字典中的单词互不相同,且 ``beginWord != endWord``。 自建示例 -------- * ``cold`` 到 ``warm``,字典为 ``["cord", "card", "ward", "warm", "bold"]``:最短序列 ``cold -> cord -> card -> ward -> warm`` 含五个单词,返回 ``5``; * ``hit`` 到 ``cog``,字典为 ``["hot", "dot", "dog"]``:终点不在字典中,返回 ``0``; * ``aaa`` 到 ``aab``,且字典含 ``aab``:两词直接相连,返回 ``2``,不是变换次数 ``1``。 C++ 实现 -------- .. code-block:: cpp #include #include #include #include #include class Solution { private: bool differsByOne(const std::string& first, const std::string& second) { int differences = 0; for (int index = 0; index < static_cast(first.size()); ++index) { if (first[index] != second[index]) { ++differences; if (differences > 1) { return false; } } } return differences == 1; } int scanDictionaryForEveryNode( const std::string& beginWord, const std::string& endWord, const std::vector& wordList ) { std::unordered_set unused(wordList.begin(), wordList.end()); if (!unused.count(endWord)) { return 0; } std::queue queue; queue.push(beginWord); unused.erase(beginWord); int sequenceLength = 1; while (!queue.empty()) { int levelSize = static_cast(queue.size()); while (levelSize-- > 0) { const std::string word = queue.front(); queue.pop(); if (word == endWord) { return sequenceLength; } for (auto it = unused.begin(); it != unused.end();) { if (differsByOne(word, *it)) { queue.push(*it); it = unused.erase(it); } else { ++it; } } } ++sequenceLength; } return 0; } int bfsWithGeneratedNeighbors( const std::string& beginWord, const std::string& endWord, const std::vector& wordList ) { std::unordered_set unused(wordList.begin(), wordList.end()); if (!unused.count(endWord)) { return 0; } std::queue queue; queue.push(beginWord); unused.erase(beginWord); int sequenceLength = 1; while (!queue.empty()) { int levelSize = static_cast(queue.size()); while (levelSize-- > 0) { std::string word = queue.front(); queue.pop(); if (word == endWord) { return sequenceLength; } for (int index = 0; index < static_cast(word.size()); ++index) { const char original = word[index]; for (char ch = 'a'; ch <= 'z'; ++ch) { word[index] = ch; if (unused.erase(word)) { queue.push(word); } } word[index] = original; } } ++sequenceLength; } return 0; } int bidirectionalBfs( const std::string& beginWord, const std::string& endWord, const std::vector& wordList ) { std::unordered_set unused(wordList.begin(), wordList.end()); if (!unused.count(endWord)) { return 0; } std::unordered_set front{beginWord}; std::unordered_set back{endWord}; unused.erase(beginWord); unused.erase(endWord); int sequenceLength = 2; while (!front.empty() && !back.empty()) { if (front.size() > back.size()) { front.swap(back); } std::unordered_set nextFront; for (std::string word : front) { for (int index = 0; index < static_cast(word.size()); ++index) { const char original = word[index]; for (char ch = 'a'; ch <= 'z'; ++ch) { word[index] = ch; if (back.count(word)) { return sequenceLength; } if (unused.erase(word)) { nextFront.insert(word); } } word[index] = original; } } front = std::move(nextFront); ++sequenceLength; } return 0; } public: int ladderLength( std::string beginWord, std::string endWord, std::vector& wordList ) { return bidirectionalBfs(beginWord, endWord, wordList); } }; 题解 ---- 从原始搜索空间开始 ~~~~~~~~~~~~~~~~~~ 一个状态是当前单词,一步选择是修改某个位置为另一个字母。若不做约束,长度为 ``L`` 的小写单词共有 ``26^L`` 个;题目给出的字典把可进入状态限制为有限集合。把合法单词看成节点,恰好相差一个字母的两个 节点之间连边,每条边都代表一次等价的变换,问题就成为无权图最短路。 DFS 适合寻找“是否存在路径”,却不能保证第一条到达终点的路径最短,还要处理环和全局最优值。BFS 按距 起点的边数逐层扩展,因此首次到达终点时,所有更短层都已检查,得到的必是最短长度。 方案一:对每个节点扫描剩余字典 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 最直接的邻居查找方式,是从当前单词出发,逐个比较所有尚未访问的字典单词。``differsByOne`` 统计不同 位置,恰好一个不同时就是邻居;``scanDictionaryForEveryNode`` 将发现的单词立即入队并从 ``unused`` 删除。 删除是安全的,因为本题只求长度,不需要像“单词接龙 II”那样保留同层多前驱。一个单词第一次被 BFS 发现时距离已经最短;以后再到达只会得到相同或更长距离,不可能改善最终答案。入队即删还能阻止同一层把 它重复加入队列。 该方案把图定义直接翻译成比较,但若最终访问 ``N`` 个单词,每个节点又扫描大部分字典,重复工作接近 ``O(N^2L)``:绝大多数比较只是再次确认两个单词不是邻居。 方案二:反过来生成所有可能邻居 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 题目提供了比“两词是否相邻”更强的结构:邻居必须只改一个位置,而每个位置只有 26 种字母。对当前单词 依次替换每个字符,再用哈希集合判断候选是否存在,只需检查 ``O(26L)`` 个模式,不再扫描整个字典。 ``bfsWithGeneratedNeighbors`` 中 ``unused.erase(word)`` 同时完成成员判断与访问标记:返回非零表示候选原本 存在且是第一次发现,于是入队;返回零表示候选不在字典或已经访问,不再处理。循环也会尝试原字母,但原 单词早已从 ``unused`` 删除,因此不会产生自环。 BFS 层数映射到返回值 ~~~~~~~~~~~~~~~~~~~~ ``sequenceLength`` 表示当前队列层中任一单词对应的序列长度。初始队列只有起点,所以从 ``1`` 开始;完成 整层后增加一。若 ``aaa`` 在第一层生成 ``aab``,``aab`` 位于第二层,出队时返回 ``2``。这里返回的是 单词数,不是边数,初始化为零会造成统一的少一错误。 方案三:从两端压缩搜索前沿 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 单向 BFS 的距离已经最优,但当每个节点有许多邻居、最短路径较深时,前沿会呈指数式膨胀。因为变换关系 是无向的,可以同时维护起点侧 ``front`` 和终点侧 ``back``;每扩展一层,就让已计入的序列长度增加一, 生成候选落入另一侧当前前沿时,两段路径接合。 代码始终扩展节点数较少的一侧。``front.swap(back)`` 只交换搜索方向,不改变两侧已经扩展的总层数; ``sequenceLength`` 记录的是两侧深度之和加上两个端点,因此仍在每轮统一递增。未访问集合由两侧共享,任一 单词被某侧发现后立即删除,避免两棵搜索树内部重复展开。 具体走读 ~~~~~~~~ 以 ``cold`` 到 ``warm`` 为例,忽略无关分支: .. list-table:: :header-rows: 1 * - 待连接长度 - 扩展前沿 - 生成结果 * - 2 - 起点侧 ``{cold}`` - ``{cord, bold}`` * - 3 - 终点侧 ``{warm}`` - ``{ward}`` * - 4 - 终点侧 ``{ward}`` - ``{card}`` * - 5 - 较小的一侧生成 ``cord`` 或 ``card`` - 命中另一前沿,返回 ``5`` 实际扩展哪一侧由集合大小决定,不要求严格交替。关键不变量是:``front``、``back`` 分别代表两棵 BFS 树 尚待连接的最浅边界;只有整层生成完才用 ``nextFront`` 替换当前边界。 主解选择与复杂度 ~~~~~~~~~~~~~~~~ 公开入口采用双向 BFS。它比单向方案多维护一个前沿并增加相遇长度的推理成本,但在常见分支较多的图中能 显著减少实际访问节点;若更重视实现简洁,``bfsWithGeneratedNeighbors`` 是同样正确的稳健方案。逐词扫描 只保留为原始基线,因为它没有利用单字符变化结构。 设访问节点数为 ``N``、单词长度为 ``L``。逐词扫描最坏时间 ``O(N^2L)``。按需生成邻居时,每个节点尝试 ``26L`` 个候选,字符串构造和哈希需要 ``O(L)``,期望时间 ``O(26NL^2)``,空间 ``O(NL)``。双向 BFS 不改变最坏渐进上界,但通常把搜索深度从约 ``d`` 分摊到两端,实际前沿远小于单向搜索。