127. 单词接龙

Difficulty
Hard
Tags
BFS
URL
https://leetcode-cn.com/problems/word-ladder/
Star
字典 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 中的所有字符串 互不相同
通过次数120,235提交次数257,451

法1 BFS

典型的宽度优先搜索题目。
从当前单词选择下一轮备选单词时，采用如下方案：
for i in range(len(cur)):
    for newChar in range(97, 123):
        newWord = cur[0:i] + chr(newChar) + cur[i+1:]
添加visited数组来讲访问过的单词添加进去，且添加到visited的时间有以下两种：
  • 添加到下一轮队列的时候就加进去
  • 开始本轮时，将本轮的所有备选加进去
题解
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        queue = []
        queue.append(beginWord)
				# 将 单词列表转化为集合，要比双向BFS快很多很多!!!
        wordList = set(wordList)
        step = 0
        while queue:
            step += 1
            size = len(queue)
            while size > 0:
                cur = queue.pop(0)
                size -= 1
                if cur == endWord:
                    return step
                # 构造新单词
                for i in range(len(cur)):
                    for newChar in range(97, 123):
                        newWord = cur[0:i] + chr(newChar) + cur[i+1:]
                        if newWord in wordList:
                            queue.append(newWord)
                            wordList.remove(newWord)
        return 0

双向BFS

区别于单向BFS，双向BFS具有更高效的搜索策略。双向BFS的目标不再是一个简单的目标，而是一个目标队列，只要两边的队列有交集即认为达到目标了。
每一轮开始都倾向于选择备选节点少的队列。
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordList = set(wordList)
        if endWord not in wordList:
            return 0

        begin_queue = set()
        end_queue = set()

        begin_queue.add(beginWord)
        end_queue.add(endWord)
        
        wordList.remove(endWord)
        res = 0
        while begin_queue and end_queue:
            res += 1
            # 用于存放当前队列中节点的邻居
            temp_queue = set()
            temp_len = len(begin_queue)

            while temp_len > 0:
                # 随机移除一个元素,此处是可以随机移除的，因为这都是begin_queue中节点的邻居，邻居都在同一层上，没有先后之分
                curWord = begin_queue.pop()
                temp_len -= 1
                
                # 找到该节点的相邻节点
                for i in range(0, len(curWord)):
                    for c in [chr(n) for n in range(97, 123)]:
                        newWord = curWord[0:i] + c + curWord[i+1:]
                        # 相邻节点在对面，那就直接返回res + 1
                        # 因为判断的是当前节点的邻居节点是否在end_queue中，这本身也算一步,所以+1
                        if newWord in end_queue:
                            return res + 1

                        if newWord in wordList:
                            temp_queue.add(newWord)
                            wordList.remove(newWord)

            # 下一轮开始选择长度最少的，以节省 搜索空间
            if len(end_queue) < len(temp_queue):
                begin_queue = end_queue
                end_queue = temp_queue
            else:
                begin_queue = temp_queue

        return 0