A transformation sequence from word beginWord
to word endWord
using a dictionary wordList
is a sequence of words beginWord -> s1 -> s2 -> ... -> sk
such that:
si
for 1 <= i <= k
is in wordList
. Note that beginWord
does not need to be in wordList
.sk == endWord
Given two words, beginWord
and endWord
, and a dictionary wordList
, return all the shortest transformation sequences from beginWord
to endWord
, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk]
.
For example:
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
Explain your approach and provide the code.
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The goal is to find all the shortest sequences of words that transform a starting word into an ending word, changing only one letter at a time. The brute force approach explores every possible word sequence until all valid transformations are found.
Here's how the algorithm would work step-by-step:
def find_ladders_brute_force(start_word, end_word, word_list):
all_sequences = []
shortest_length = float('inf')
def find_sequences(current_word, current_sequence):
nonlocal shortest_length, all_sequences
# If we've found the end word, add the sequence
if current_word == end_word:
if len(current_sequence) <= shortest_length:
if len(current_sequence) < shortest_length:
all_sequences = []
shortest_length = len(current_sequence)
all_sequences.append(current_sequence.copy())
return
# Explore neighbor words.
for next_word in word_list:
if differ_by_one_letter(current_word, next_word):
#Avoid cycles by only exploring unvisited words
if next_word not in current_sequence:
current_sequence.append(next_word)
find_sequences(next_word, current_sequence)
current_sequence.pop()
def differ_by_one_letter(word1, word2):
if len(word1) != len(word2):
return False
difference_count = 0
for i in range(len(word1)):
if word1[i] != word2[i]:
difference_count += 1
return difference_count == 1
find_sequences(start_word, [start_word])
return all_sequences
The Word Ladder II problem asks for all shortest transformation sequences between two words, changing one letter at a time, using a provided word list. The optimal approach leverages Breadth-First Search (BFS) to find shortest paths and keeps track of all possible paths that lead to a solution. This ensures that we only explore paths that are potentially the shortest, avoiding longer paths that would lead to unnecessary computation.
Here's how the algorithm would work step-by-step:
from collections import deque
def find_ladders(begin_word, end_word, word_list):
word_set = set(word_list)
if end_word not in word_set:
return []
neighbors = {}
word_set.add(begin_word)
for word in word_set:
neighbors[word] = []
for i in range(len(word)):
for char_code in range(ord('a'), ord('z') + 1):
new_char = chr(char_code)
new_word = word[:i] + new_char + word[i+1:]
if new_word in word_set and new_word != word:
neighbors[word].append(new_word)
queue = deque([(begin_word, [begin_word])])
visited = {begin_word: 1}
result = []
min_length = float('inf')
while queue:
current_word, current_path = queue.popleft()
if len(current_path) > min_length:
continue
if current_word == end_word:
min_length = len(current_path)
# Only add the path if it's the shortest
if len(current_path) == min_length:
result.append(current_path)
continue
# Explore neighbors to discover new paths.
for neighbor in neighbors[current_word]:
if neighbor not in visited or visited[neighbor] >= len(current_path) + 1:
# We use visited to avoid cycles and shorter paths
visited[neighbor] = len(current_path) + 1
queue.append((neighbor, current_path + [neighbor]))
return result
Case | How to Handle |
---|---|
beginWord or endWord is null or empty | Return an empty list if beginWord or endWord is null or empty as no transformation is possible. |
wordList is null or empty | Return an empty list if the wordList is null or empty, indicating no possible transformations. |
beginWord is not in the wordList | Add beginWord to the wordList to allow it to be the start of a valid sequence, or return empty list if explicitly disallowed by requirements. |
endWord is not in the wordList | Return an empty list since the endWord must be present to reach a valid word ladder. |
beginWord and endWord are the same | If beginWord and endWord are the same, and wordList contains beginWord, return a list containing only beginWord; otherwise, return an empty list. |
No possible word ladder exists | The BFS will explore all possible paths, and if the endWord is never reached, an empty list will be returned. |
Very large wordList causing memory issues | Consider using an iterative deepening depth-first search (IDDFS) to limit memory consumption if BFS becomes problematic with large word lists. |
Word ladder length exceeds maximum allowed length | If there's a maximum allowed length specified, prune BFS paths exceeding this length to improve performance. |