单词接龙问题

本文参考代码随想录

字典 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” 不在字典中，所以无法进行转换。

classSolution:defladderLength(self,beginWord:str,endWord:str,wordList:List[str])->int:iflen(wordList)==0orendWordnotinwordList:return0wordSet=set(wordList)# 优化查找效率q=collections.deque()q.append(beginWord)mapping={beginWord:1}whileq:cur=q.popleft()cur_step=mapping[cur]foriinrange(len(cur)):forjinrange(26):c=chr(ord('a')+j)new_word=list(cur)new_word[i]=c new_word=''.join(new_word)ifnew_word==endWord:returncur_step+1ifnew_wordinwordSetand(new_wordnotinmapping):q.append(new_word)mapping[new_word]=cur_step+1return0