字典 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 中的所有字符串 互不相同
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-ladder
参考:
# 0127.单词接龙 class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: [str]) -> int: """ 无向图,BFS :param beginWord: :param endWord: :param wordList: :return: """ from typing import List from collections import deque wordSet = set(wordList) if len(wordSet) == 0 or endWord not in wordSet: return 0 if beginWord in wordSet: wordSet.remove(beginWord) queue = deque() queue.append(beginWord) visited = set(beginWord) wordLen = len(beginWord) step = 1 while queue: curSize = len(queue) for i in range(curSize): word = queue.popleft() word_list = list(word) for j in range(wordLen): originChar = word_list[j] for k in range(26): word_list[j] = chr(ord('a')+k) next_word = "".join(word_list) if next_word in wordSet: if next_word == endWord: return step + 1 if next_word not in visited: queue.append(next_word) visited.add(next_word) word_list[j] = originChar step += 1 return 0
待完善