127. Word Ladder
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation 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
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
解题要点:
用一个dict记录所有wordList里的字符组合(eg. hit: "#it", "h#t", "hi#"),如有分享同样字符,加到同一个字符key里。然后从startWord开始放进queue,再次根据字符组合到dict里寻找符合下一步的字。找到后检测是否等于endWord,如是,返回level + 1;若不是,检测是否visited,加进queue,并在level上增加1。
class Solution(object):
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
n = len(beginWord)
wordDict = dict()
for word in wordList:
for i in range(n):
key = word[:i] + "#" + word[i+1:]
if key in wordDict:
wordDict[key].append(word)
else:
wordDict[key] = [word]
# print wordDict
visited = {}
for wor in wordList:
visited[wor] = 0
queue = [(beginWord, 1)]
while queue:
w, level = queue.pop(0)
for j in range(n):
key1 = w[:j] + "#" + w[j+1:]
if key1 in wordDict:
for wo in wordDict[key1]:
if wo == endWord:
return level + 1
if visited[wo] == 0:
visited[wo] = 1
queue.append((wo, level + 1))
wordDict[key1] = []
return 0
Last updated
Was this helpful?