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

牛群最短移动序列

https://www.nowcoder.com/practice/6473462e05ac4665baec04caf628abdd

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

    将 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
牛客高频top202题解系列 文章被收录于专栏

记录刷牛客高频202题的解法思路

全部评论

相关推荐

嵌入式求职之路:可以看我经验😂,https://www.nowcoder.com/share/jump/73221730841876945
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务