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 .
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.
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