Description
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.
Solutions
1. BFS
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
wordList = set(wordList)
visited = set()
queue = collections.deque([(beginWord, 1)])
alpha = string.ascii_lowercase # 'abcd...z'
while queue:
word, length = queue.popleft()
if word == endWord:
return length
n = len(word)
for i in range(n):
for ch in alpha:
newWord = word[:i] + ch + word[i+1:]
if newWord in wordList and newWord not in visited:
queue.append((newWord, length+1))
visited.add(newWord)
return 0
# Runtime: 420 ms, faster than 37.62% of Python online submissions for Word Ladder.
# Memory Usage: 12.9 MB, less than 75.68% of Python online submissions for Word Ladder.
2. Bidirectional BFS
3. DFS
第一个想法总是用 DFS 回溯，其实也可以做，但是这里不合适，因为要求是求最短的路径，如果是回溯的话会优先往深了找，这样会超时。