# 单词接龙
字典 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 <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord、endWord 和 wordList[i] 由小写英文字母组成beginWord != endWordwordList 中的所有字符串 互不相同
## template
```python
class Solution:
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
if endWord not in wordList:
return 0
if beginWord in wordList:
wordList.remove(beginWord)
wordDict = dict()
for word in wordList:
for i in range(len(word)):
tmp = word[:i] + "_" + word[i + 1 :]
wordDict[tmp] = wordDict.get(tmp, []) + [word]
stack, visited = [(beginWord, 1)], set()
while stack:
word, step = stack.pop(0)
if word not in visited:
visited.add(word)
if word == endWord:
return step
for i in range(len(word)):
tmp = word[:i] + "_" + word[i + 1 :]
neigh_words = wordDict.get(tmp, [])
for neigh in neigh_words:
if neigh not in visited:
stack.append((neigh, step + 1))
return 0
```
## 答案
```python
```
## 选项
### A
```python
```
### B
```python
```
### C
```python
```