Leetcode 127 Word Ladder
https://leetcode.com/problems/word-ladder/description
Our idea is simple, for each word, we find all the possible variations by changing only 1 letter and check if the variation is equal to the endWord. The problem is asking us to find the shortest transformation sequence, I first thought of BFS. But why BFS?
First of all, the way BFS works is to look at the nodes at each “level” or a certain distance from the original node, e.g given a word, the next level is all the variations of the the word by changing 1 letter, their distance is exactly 1 more than the current word from the original word.
More important, BFS is suited for finding the smallest distance from the original node. As soon as we see the node that meets the requirements, it’s guaranteed to be the nearest node from the original node because we are checking the nodes by their distance from the original node on ascending order.
Let’s take a look at the solution
class Solution:
def get_all_veriations(self, word, word_set):
result = []
for i in range(len(word)):
left, right = word[:i], word[i+1:]
for char in "abcdefghijklmnopqrstuvwxyz":
variation = left + char + right
if variation in word_set:
result.append(variation)
return result
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
word_set = set(wordList)
queue = collections.deque([beginWord])
visited = { beginWord: 1 }
while queue:
word = queue.popleft()
variations = self.get_all_veriations(word, word_set)
for variation in variations:
if variation == endWord:
return visited[word] + 1
if variation in visited:
continue
if variation in word_set:
queue.append(variation)
visited[variation] = visited[word] + 1
return 0