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]
.
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.
Constraints:
1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 500
wordList[i].length == beginWord.length
beginWord
, endWord
, and wordList[i]
consist of lowercase English letters.beginWord != endWord
wordList
are unique.105
.This problem asks to find all shortest transformation sequences from a beginWord
to an endWord
, given a dictionary wordList
. A transformation sequence is a series of words where each word differs from the previous word by only one letter.
The optimal approach is to use Breadth-First Search (BFS) combined with backtracking. Here's a breakdown:
1. BFS for Shortest Paths:
beginWord
to endWord
. BFS guarantees that we find the shortest path first.dist
map to store the distance of each word from the beginWord
.q
is used to process words level by level.2. Tracking Predecessors:
prev
map (a dictionary in Python, a HashMap in Java, or a map in Go) to store the set of words that can directly precede a given word in a shortest path.3. Backtracking for All Paths:
endWord
, we perform backtracking to reconstruct all shortest paths.dfs
function starts from endWord
and explores its predecessors using the prev
map.ans
list when it reaches beginWord
.Time Complexity Analysis:
wordList
, so the time complexity of BFS is O(M * L), where M is the length of wordList
and L is the length of each word.Space Complexity Analysis:
dist
, prev
: These maps store at most M words, each with a constant amount of extra information (distance and predecessors). Thus, their space complexity is O(M).q
: The queue can hold up to M words at a time, so its space complexity is O(M).ans
: The space used by ans
depends on the number of shortest paths. This can vary greatly based on the input.ans
is not considered in the Big O notation because it is dependent on the input data rather than a function of the input size.Code Example (Python):
from collections import defaultdict, deque
class Solution:
def findLadders(self, beginWord, endWord, wordList):
# ... (BFS and backtracking implementation as described above) ...
Key improvements in the provided code:
words
set to track visited words and removing them efficiently.endWord
is not in wordList
or no transformation sequence exists.The Java and Go code follow the same algorithm but adapt the data structures and syntax of their respective languages. The underlying logic for BFS and backtracking remains consistent.