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.
For example,
- Given:
- beginWord = "hit"
- endWord = "cog"
- wordList = ["hot","dot","dog","lot","log","cog"]
- As one shortest transformation is
"hit" -> "hot" -> "dot" -> "dog" -> "cog", - return its length 5.
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.
Python Solution 1:
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
d = collections.defaultdict(set)
for word in wordList:
for i in range(len(word)):
key = word[:i] + '_' + word[i + 1:]
d[key].add(word)
l = set([beginWord])
r = set()
res = 1
while l:
for w in l:
for i in range(len(w)):
key = w[:i] + '_' + w[i + 1:]
if endWord in d[key]: return res + 1
r.update(d[key])
del d[key]
l = set(r)
r = set()
res += 1
return 0
Python Solution 2:
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
wordList = set(wordList)
if endWord not in wordList: return 0
l = [beginWord]
res = 1
while l:
print l
r = []
res += 1
for w in l:
for i in range(len(w)):
for j in range(26):
_w = w[:i] + chr(ord('a') + j) + w[i + 1:]
if _w in wordList:
if _w == endWord: return res
r.append(_w)
wordList.remove(_w)
l = r
return 0
Summary:
- Solution 1 is 272ms, while Solution 2 is 952ms
LeetCode: 127. Word Ladder
近期评论