单词接龙

难度: Hard

在字典（单词列表） wordList 中，从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。

给定两个长度相同但内容不同的单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同

注意：本题与主站 127 题相同： https://leetcode-cn.com/problems/word-ladder/

Submission

运行时间: 61 ms

内存: 16.8 MB

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordDict, step = set(wordList), 1
        if endWord not in wordDict:
            return 0

        s1, s2 = set([beginWord]), set([endWord])
        while s1:
            stack = set([])
            wordDict -= s1

            for s in s1:
                for i in range(len(beginWord)):
                    for j in string.ascii_lowercase:
                        tmp = s[:i] + j + s[i+1:]
                        if tmp not in wordDict:
                            continue
                        if tmp in s2:
                            return step + 1
                        stack.add(tmp)

            if len(stack) < len(s2):
                s1 = stack
            else:
                s1, s2 = s2, stack
            step += 1
        return 0

Explain

这道题可以使用双向广度优先搜索（Bidirectional BFS）来解决。思路是从起始单词和结束单词同时开始搜索，每次都扩展当前层的单词，直到两边相遇。这样可以大大减少搜索的范围，从而提高效率。在搜索过程中，每次都尝试改变当前单词的每个字母，看是否能得到字典中的单词，如果能，则加入下一层的搜索队列中。当发现某个变换后的单词同时出现在从起始单词和结束单词扩展的集合中时，说明找到了最短路径。

时间复杂度: O(N*L)

空间复杂度: O(N)

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordDict, step = set(wordList), 1
        if endWord not in wordDict:
            return 0

        s1, s2 = set([beginWord]), set([endWord])
        while s1:
            stack = set([])
            wordDict -= s1

            for s in s1:
                for i in range(len(beginWord)):
                    for j in string.ascii_lowercase:
                        tmp = s[:i] + j + s[i+1:]
                        if tmp not in wordDict:
                            continue
                        if tmp in s2:
                            return step + 1
                        stack.add(tmp)

            if len(stack) < len(s2):
                s1 = stack
            else:
                s1, s2 = s2, stack
            step += 1
        return 0

Explore

双向广度优先搜索（Bidirectional BFS）是一种有效的搜索策略，用于从两个方向（起始点和终点）同时进行搜索，以加快搜索速度和提高效率。这种方法的优势在于它可以显著减少需要探索的状态数。单向搜索可能需要遍历大量路径才能到达目标，而双向搜索通过同时从起点和终点向对方进展，使得搜索路径在中间某处相遇，从而减少了搜索路径的长度。一旦两个搜索方向在中间相遇，搜索可以立即停止，这通常会比单向搜索到达终点更快，特别是在状态空间很大时。

在双向广度优先搜索中，两个搜索集合中的每一个都只扩展到当前层级的单词。当某个单词同时出现在两个集合中时，意味着从起点到该单词和从终点到该单词的路径都是最短的，因为广度优先搜索保证了每次扩展都是在当前最短的路径上进行。两个最短路径在某个单词处相遇，因此，这个相遇点代表了从起点到终点的最短路径的连接点。从这个连接点将两边的路径合并，自然形成了整体的最短路径。

操作`wordDict -= s1`的目的是从单词字典中移除已经被当前层处理过的单词。这样做主要是为了防止在后续的搜索中重复考虑这些单词，从而避免创建无效或重复的路径，确保搜索的效率。潜在的影响包括减少了搜索空间，这有助于提高搜索速度，但这也意味着一旦这些单词被移除，它们将不会在任何后续的搜索中被考虑，即使在某些情况下重新考虑它们可能有助于找到其他有效路径。然而，在本题的上下文中，这种影响是积极的，因为我们只关心找到任何有效的最短路径。