Leetcode 127 Word Ladder
https://leetcode.com/problems/word-ladder/description
This problem can be solved by BFS for a couple of reasons:
- At each word, there are multiple paths to take to go to the next word
- It’s trying to find the shortest path from
beginWordtoendWord
Based on our BFS template, at each step(word), we need to find the possible neighbors(next word given only one letter is changed and it’s in the wordList). This is probably the trickiest part of the problem but we can simply loop through each position of the word, and replace the letter with all possible variations from a-z and check if the new word is in the wordList
Then the BFS part is just same old same. Except that we for the visited variable, we will use a dictionary instead of a set to record the distance from the startWord as well.
At the end, we need to check if the endWord is in the visited, if not it means it cannot be reached so we return 0, otherwise we return visited[endWord]
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 in visited:
continue
if variation in word_set:
queue.append(variation)
visited[variation] = visited[word] + 1
if endWord in visited:
return visited[endWord]
else:
return 0
Pingback: Breadth First Search(BFS) - Leetcode Solution