迟到的双向广搜

双向广搜

这个算法很早之前就了解过了,一直没有写过,今天重新学习一遍。

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 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" 不在字典中，所以无法进行转换。

class Solution:

    def check(self, s1: str, s2: str) -> bool:
        cnt = 0
        for c1, c2 in zip(s1, s2):
            if c1 != c2:
                cnt += 1
        return cnt == 1

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in set(wordList):
            return 0
        q1, q2 = deque(), deque()
        mp1, mp2 = {}, {}
        mp1[beginWord] = 1
        mp2[endWord] = 1
        q1.append(beginWord)
        q2.append(endWord)
        while q1 and q2:
            i = 0
            if len(q1) <= len(q2):
                i = self.bfs(q1, mp1, mp2, wordList)
            else:
                i = self.bfs(q2, mp2, mp1, wordList)
            if i != -1:
                return i
        return 0

    # 核心代码
    def bfs(self, q: Deque, mp1: dict, mp2: dict, wordList: List[str]) -> int:
        sz = len(q)
        while sz:
            s = q.popleft()
            if s in mp2:
                return mp1[s] + mp2[s] - 1
            for word in wordList:
                if word not in mp1 and self.check(word, s):
                    mp1[word] = mp1[s] + 1
                    q.append(word)
            sz -= 1
        return -1