1. Title Description

Give two words （beginWord and endWord） And a dictionary , Find out from beginWord To endWord The length of the shortest transformation sequence . The conversion should follow the following rules ：

Only one letter can be changed at a time .
The middle word in the conversion process must be the word in the dictionary .
explain :
If there is no such conversion sequence , return 0.
All words have the same length .
All words consist of lowercase letters only .
There are no duplicate words in the dictionary .
You can assume beginWord and endWord It's not empty , And they are different .

Example 1:
Input :
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
Output : 5
explain : One of the shortest conversion sequences is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
Return its length 5.

Example 2:
Input :
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
Output : 0
explain : endWord “cog” Not in the dictionary , So there's no conversion .

2. Ideas

The main method is to use the queue to achieve breadth first search . Find the words in the dictionary that are one letter different from the current one and join the team , Then go through the words , Until I find endWord.

1. First construct a string queue , And will beginWord Join the queue .
2. Make a single character replacement for the queue header string after each replacement , To judge whether or not and endWord matching , If the match , return res, There is no match , Look at the word in the dictionary .
3. If there is , Then add the string to the queue , At the same time, delete the string from the dictionary .
4. repeat , Until and endWord matching . If the last queue is empty, it has not been matched to , Then return to 0.

If you are directly in wordList If you look in , Will timeout .set The time complexity of finding a word in is O(log(n)), Than list fast .

class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
queue = [beginWord]
res = 1
wordList = set(wordList)
while queue:
for a in range(len(queue)):
curstr = queue.pop(0)
curstrlen = len(curstr)
for i in range(curstrlen):
for x in range(ord('a'), ord('z') + 1):
# Replace 26 English letters with a letter of the current string 
temp = curstr[:i] + chr(x) + curstr[i+1:]
if temp == endWord and temp in wordList:
return res + 1
elif temp != endWord and temp in wordList:
queue.append(temp)
wordList.remove(temp)
res += 1
return 0