leetcode:126. 单词接龙 II

126. 单词接龙 II

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/word-ladder/

按字典 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 中的所有单词 互不相同

解法

• 广度优先遍历BFS+DFS回溯：经过分析可知，题目要求将一个基因序列 A变化至另一个基因序列 B，需要满足一下条件：
  • 序列 A 与 序列 B 之间只有一个字符不同；
  • 变化字符只能从26个小写字母中进行选择；
  • 变换后的序列 B 一定要在字符串数组 wordlist 中， 可以将wordlist转成set加快速度；
    

求“最短路径”、“最小深度”——BFS
每个单词节点有自己的层，它的“邻居”是它可变成的单词，属于下一层。
这很像 BFS：考察当前层出列的节点，带出下一层的节点入列。

怎么找到自己的 “邻居单词”
让单词的每个字母逐个改动，生成25个新单词。选出存在于wordList的，就是“邻居单词”。

路径上出现过的单词，就不要让它再出现
比如：hit->hot->hit ，又变回来，即重复访问节点，徒增路径长度。用一个 visited 容器，记录遍历过的单词节点。

为什么还需要 DFS？
如果是求最短路径的长度，仅 BFS 即可。但要找出最短路径的所有组合，则需要回溯。

我们可以从起点词开始DFS，也可以从终点词开始 DFS，我选择后者，遇到起点词，就找到一条满足条件的路径，推入结果数组，然后回溯，直到找出所有最短路径。

DFS 需要哪些信息？

• 需要知道当前节点的“父亲们”，它可以从哪些单词变过来——需要wordMap。
• 根据当前节点的“父亲们”的所在层数，选出满足最短路径的——需要levelMap。
• 我们在 BFS 时要构建这种关系，供 DFS 时使用。

BFS 具体做法

• 遍历当前层的单词，逐个出列，将它的字母逐个改动成 a 到 z，找出存在于单词表的新单词。
• 新单词作为 key 存到 wordMap，值是它的“父单词”，即出列的单词。
• 如果这个新单词正好是终点词，说明肯定存在有路径可以变到终点词。
• 用 levelMap 记录路径上的单词所在的层。
• 将下一层的新单词入列，下次循环全都是下一层的单词
• 用 visited 表记录访问过的单词，避免将它重复加入到路径中

DFS 怎么写

• DFS 目的是找出最短路径的所有组合，用 path 数组表示当前的路径。
• DFS 将节点推入 path 数组的开头，满足要求的节点，继续递归，不符合要求的，要回溯
• DFS 的出口：遍历到了起点词，说明一条满足条件的路径生成好了，推入 res 数组

怎么理解回溯，为什么要回溯

• 回溯就是遇到不满足条件的节点，要 “掉头”，回到选择前的状态，考察别的选择。
• 一个单词可能有很多“邻居单词”可选择，但为了路径最短，需要选择满足「当前单词的层 == 邻居单词的层 + 1」的节点，这才是最短路径中的节点。

代码实现

BFS + DFS

python实现

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        if beginWord == endWord:
            return []
 
        wordSet = set(wordList)
        wordSet.add(beginWord)

        if endWord not in wordSet:
            return []

        levelMap = dict()
        wordMap = dict()
        visited = set()
        visited.add(beginWord)

        level = 0
        levelMap[beginWord] = level

        finished = False

        queue = [beginWord]
        while queue:
            level_size = len(queue)
            level += 1
            for _ in range(level_size):
                word = queue.pop(0)
                for i, x in enumerate(word):
                    for y in 'abcdefghijklmnopqrstuvwxyz':
                        if y == x:
                            continue
                        
                        nxt_word = word[:i] + y + word[i+1:]

                        if nxt_word not in wordSet:
                            continue
                        
                        if nxt_word in wordMap:
                            wordMap[nxt_word].append(word)
                        else:
                            wordMap[nxt_word] = [word]
                        
                        if nxt_word in visited:  # 注意visited不能加在最开始，不然wordMap和wordSet得不到更新
                            continue
                        
                        if nxt_word == endWord:
                            finished = True

                        levelMap[nxt_word] = level
                        visited.add(nxt_word)
                        queue.append(nxt_word)
        
        if not finished:
            return []
        

        res = []

        def dfs(path, beginWord, word):
            if word == beginWord:
                res.append([beginWord] + path)
                return
            
            if word in wordMap:
                for parent in wordMap[word]:
                    if levelMap[parent] + 1 == levelMap[word]:
                        dfs([word]+path, beginWord, parent)
        
        dfs([], beginWord, endWord)
        return res

参考

• https://leetcode.cn/problems/word-ladder-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-3-3/
• https://leetcode.cn/problems/word-ladder-ii/solution/ru-guo-ni-fa-xian-kan-bie-ren-de-ti-jie-kan-bu-don/