127 - Word Ladder
Written on October 21, 2015
Tweet
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: Only one letter can be changed at a time. Each intermediate word must exist in the dictionary.
from collections import defaultdict
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
word_dict = defaultdict(list)
for word in wordList:
for i in range(len(word)):
new_word = word[:i] + "_" + word[i+1:]
word_dict[new_word].append(word)
queue = [(beginWord, 1)]
seen = set()
while queue:
curr, step = queue.pop(0)
seen.add(curr)
if curr == endWord:
return step
for i in range(len(curr)):
new_word = curr[:i] + "_" + curr[i+1:]
for candidate in word_dict[new_word]:
if candidate not in seen:
queue.append((candidate, step + 1))
return 0