题解 | #牛群最短移动序列#

• 题目考察的知识点 : 广度优先搜索, 哈希
• 题目解答方法的文字分析：

将 beginWord 加入队列 queue 并将其标记为已访问 visited。然后进行如下操作：

1. 取出队列头部元素 curr。
2. 如果 curr 等于 endWord，则返回步数 step。
3. 否则遍历 wordList 中的每个单词 word，如果 word 与 curr 只差一个字符，并且没有被访问过，则将 word 加入队列并标记为已访问 visited。
4. 如果队列为空，则说明无法从 beginWord 到达 endWord，返回 0。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param beginWord string字符串
# @param endWord string字符串
# @param wordList string字符串一维数组
# @return int整型
#
from collections import deque
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        words = set(wordList)
        if endWord not in words:
            return 0

        queue = deque([(beginWord, 1)])
        visited = set([beginWord])

        while queue:
            curr, step = queue.popleft()
            if curr == endWord:
                return step
            for i in range(len(curr)):
                for j in range(26):
                    c = chr(ord("a") + j)
                    if c != curr[i]:
                        next_word = curr[:i] + c + curr[i + 1 :]
                        if next_word in words and next_word not in visited:
                            queue.append((next_word, step + 1))
                            visited.add(next_word)
        return 0