单词接龙 II

标签: 广度优先搜索 哈希表 字符串 回溯

难度: Hard

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：

  • 每对相邻的单词之间仅有单个字母不同。
  • 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
  • sk == endWord

给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。

提示：

  • 1 <= beginWord.length <= 5
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 500
  • wordList[i].length == beginWord.length
  • beginWord、endWord 和 wordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有单词 互不相同

Submission

运行时间: 28 ms

内存: 16.4 MB

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        wordList.append(beginWord)
        ### 构建具有邻接关系的桶
        buckets = defaultdict(list)
        for word in wordList:
            for i in range(len(beginWord)):
                match = word[:i] + '_' + word[i+1:]
                buckets[match].append(word)
        ##### BFS遍历
        preWords = defaultdict(list)  # 前溯词列表
        toSeen = deque([(beginWord, 1)])  # 待遍历词及深度
        beFound = {beginWord:1}  # 已探测词列表
        while toSeen:
            curWord, level = toSeen.popleft()
            for i in range(len(beginWord)):
                match = curWord[:i] + '_' + curWord[i+1:]
                for word in buckets[match]:
                    if word not in beFound:
                        beFound[word] = level+1
                        toSeen.append((word, level+1))
                    if beFound[word] == level+1:  # 当前深度等于该词首次遍历深度，则仍应加入前溯词列表
                        preWords[word].append(curWord)
            if endWord in beFound and level+1 > beFound[endWord]:  # 已搜索到目标词，且完成当前层遍历
                break
        #### 列表推导式输出结果
        if endWord in beFound:
            res = [[endWord]]
            while res[0][0] != beginWord:
                res = [[word] + r for r in res for word in preWords[r[0]]] 
            return res
        else:
            return []

Explain

这道题的解题思路是使用广度优先搜索（BFS）来寻找最短转换序列。首先，将 beginWord 加入到 wordList 中。然后构建一个桶（buckets），将 wordList 中的每个单词的每个字母都替换为下划线 '_'，生成对应的通配词，再把原单词加到对应的通配词映射的列表中。接着进行 BFS 遍历，从 beginWord 开始，每次将当前单词的每个字母都替换为下划线，在对应桶中找到所有匹配的单词，如果该单词没有被遍历过，就加入到待遍历队列（toSeen）和已探测词列表（beFound）中，同时记录下该单词的前溯词到 preWords 中。直到找到 endWord 且完成当前层的遍历，就可以结束 BFS。最后，从 endWord 出发，使用列表推导式不断遍历 preWords，生成最短转换序列的结果。

时间复杂度: O(n*l)

空间复杂度: O(n^2)

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        wordList.append(beginWord)
        ### 构建具有邻接关系的桶
        buckets = defaultdict(list)
        for word in wordList:
            for i in range(len(beginWord)):
                # 生成通配词
                match = word[:i] + '_' + word[i+1:]
                # 把单词加到通配词对应的桶中
                buckets[match].append(word)
        ##### BFS遍历
        preWords = defaultdict(list)  # 前溯词列表
        toSeen = deque([(beginWord, 1)])  # 待遍历词及深度
        beFound = {beginWord:1}  # 已探测词列表
        while toSeen:
            curWord, level = toSeen.popleft()
            for i in range(len(beginWord)):
                # 生成通配词
                match = curWord[:i] + '_' + curWord[i+1:]
                for word in buckets[match]:
                    if word not in beFound:
                        # 记录该词首次遍历到的层级
                        beFound[word] = level+1
                        toSeen.append((word, level+1))
                    if beFound[word] == level+1:  # 当前深度等于该词首次遍历深度，则仍应加入前溯词列表
                        preWords[word].append(curWord)
            if endWord in beFound and level+1 > beFound[endWord]:  # 已搜索到目标词，且完成当前层遍历
                break
        #### 列表推导式输出结果
        if endWord in beFound:
            res = [[endWord]]
            while res[0][0] != beginWord:
                # 从 endWord 回溯到 beginWord，生成转换序列
                res = [[word] + r for r in res for word in preWords[r[0]]] 
            return res
        else:
            return []

Explore

将每个字母依次替换为下划线 '_' 的方法创建了一个有效的通配符表示，这有助于快速找出所有可能的单词转换，而不需要逐一比较每个单词。这种方法减少了比较次数，提高了查找效率。例如，对于单词 'dog'，通过生成 'd_g', '_og', 'do_' 等通配词，我们可以立即获取所有只在一个位置上不同的单词，这是寻找单词变换的关键步骤。此外，这种方式也使得桶中的数据结构（即通配词到单词的映射）容易构建和查询，从而加快了整个算法的执行速度。

在广度优先搜索（BFS）中，我们通过维护一个已探测词列表（beFound）和其对应的层级来确保记录最短路径。当通过某个单词首次达到另一个单词时，我们记录这个单词的层级。如果后续再次达到这个单词但层级更高，则不再更新，因为更高的层级意味着路径更长。这样，我们可以确保每次记录的都是通过最短路径达到该单词的转换。同时，在添加前溯词时，只有当当前单词的层级正好比前溯词的层级多一时，才将前溯词添加到列表中，这保证了只有最短路径上的转换被记录。

前溯词列表preWords的管理通过检查层级来进行。当我们在BFS中遇到一个可以由多个其他单词转换而来的单词时，我们会检查每个潜在的前溯词的层级。只有当前溯词的层级正好比当前单词的层级少一，这表明从前溯词到当前单词是最短路径上的直接转换，这时才会将这个前溯词加入到preWords中。这种方式确保了preWords中只存储对构建最短路径有直接帮助的单词。