Description
Given two words beginWord and endWord, and a dictionary wordList, return the length of the 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.
- Return 0 if there is no such transformation sequence.
Example 1
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output
5
# 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
Approach
BFS-algorithm is required to solve this problem since we are to return the shortest transformation sequence from beginWord to endWord. However, this problem is not just about BFS but also about pre-processing inputs by brute-forcing every possible options which match the pair in wordList.
Solution (Python)
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
qu = [(beginWord, 1)]
size = len(beginWord)
visit = {}
permute = {}
for word in wordList:
visit[word] = False
for word in wordList:
for i in range(size):
op = word[:i] + '*' + word[i+1:]
if op not in permute:
permute[op] = [word]
else:
permute[op].append(word)
while qu:
cur, cnt = qu.pop()
visit[cur] = True
if cur == endWord:
return cnt
for i in range(size):
op = cur[:i] + '*' + cur[i+1:]
if op not in permute:
permute[op] = []
else:
for poss in permute[op]:
if visit[poss] == False:
qu.insert(0, [poss, cnt+1])
return 0
Result
Runtime : 3196ms
Memory Usage : 20.5MB
Runtime Beats 6.53% of Python Submission