leetcode:126. Word Solitaire 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
Each word node has its own layer,它的“邻居”is the word it can become,belong to the next level.
这很像 BFS：Examine the nodes that are dequeued at the current layer,Brings out the nodes of the next layer into the queue.

How to find your own “Neighbor words”
Change each letter of the word one by one,生成25个新单词.Select to exist inwordList的,就是“Neighbor words”.

Words that have appeared on the path,Just don't let it appear again
比如：hit->hot->hit ,changed back again,That is, the node is repeatedly visited,Increment path length.用一个 visited 容器,Record the word nodes traversed.

为什么还需要 DFS？
Find the length of the shortest path,仅 BFS 即可.But to find all combinations of shortest paths,则需要回溯.

We can start with starting wordsDFS,It is also possible to start with an end word DFS,我选择后者,Encounter the starting word,Find a path that satisfies the condition,推入结果数组,然后回溯,until all shortest paths are found.

DFS 需要哪些信息？

• Need to know the current node“父亲们”,What words can it come from——需要wordMap.
• 根据当前节点的“父亲们”the number of layers,Choose the one that satisfies the shortest path——需要levelMap.
• 我们在 BFS to build this relationship,供 DFS 时使用.

BFS 具体做法

• Iterate over the words of the current layer,Dequeue one by one,Change its letters one by one into a 到 z,Find new words that exist in the word list.
• new word as key 存到 wordMap,The value is it“parent word”,i.e. dequeued words.
• If the new word happens to be the terminus,It means that there must be a path that can change to the terminus.
• 用 levelMap Records the layer where the word on the path is located.
• Queues new words from the next level,The next cycle is all the words of the next layer
• 用 visited The table records visited words,Avoid adding it to the path repeatedly

DFS 怎么写

• DFS The goal is to find all combinations of shortest paths,用 path The array represents the current path.
• DFS Push the node in path 数组的开头,满足要求的节点,继续递归,不符合要求的,要回溯
• DFS 的出口：Traversed to the starting word,Indicates that a path that satisfies the condition has been generated,推入 res 数组

How to understand backtracking,为什么要回溯

• Backtracking is encountering a node that does not satisfy the condition,要 “掉头”,回到选择前的状态,考察别的选择.
• A word can have many“Neighbor words”可选择,But for the shortest path,Need to choose to satisfy「The layer for the current word == A layer of neighbor words + 1」的节点,This is the node in the shortest path.

代码实现

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:  # 注意visitedcannot be added at the beginning,不然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/