126. Word Ladder II
Problem Description
The problem presents a challenge of finding all the shortest transformation sequences that convert a beginWord
to an endWord
using a given dictionary wordList
. A transformation sequence is made up of intermediate words where each word in the sequence differs by exactly one letter from the previous word. The sequence starts with beginWord
, ends with endWord
, and each intermediate word must be found in wordList
(although beginWord
itself does not need to be in wordList
). If there is no possible transformation that leads to endWord
, the function should return an empty list.
A key point to understand is that the sequences required are the "shortest" possible. This means that if it's possible to transform beginWord
to endWord
in 4 steps, any sequences that take 5 or more steps should not be included in the output.
Flowchart Walkthrough
Let's analyze the algorithm for LeetCode 126. Word Ladder II using the provided Flowchart. Here's a step-by-step guide on how to apply the Breadth-First Search pattern:
Is it a graph?
- Yes: Each word can be considered as a node in the graph, and there is an edge between two nodes if the corresponding words can be transformed into one another by changing exactly one letter.
Is it a tree?
- No: The graph does not inherently have a hierarchical structure and can contain cycles (e.g., a word can lead to another one and potentially come back through a series of transformations).
Is the problem related to directed acyclic graphs (DAGs)?
- No: The problem is about finding the shortest transformation sequence from a start word to an end word, not about topologically sorting or working specifically with acyclic graphs.
Is the problem related to shortest paths?
- Yes: The objective is to find the shortest sequence of word transformations from the begin word to the end word. Hence, it involves finding the shortest path in a graph.
Is the graph weighted?
- No: Each edge essentially represents one transformation step, and each step is equal in "weight" or cost, implying that the graph is unweighted.
Does the problem involve connectivity?
- Yes: We need to find whether it is possible to connect the starting word to the ending word through valid word transformations.
Conclusion: Based on the Flowchart, for this unweighted shortest path problem in an unweighted graph that involves connectivity, Breadth-First Search (BFS) is the appropriate algorithm, as it is capable of exploring each level or layer of the graph efficiently and is well-suited for finding the shortest path in an unweighted graph.
Intuition
The intuition behind the solution involves two parts: first, using Breadth-First Search (BFS) to find the distance of the shortest paths from beginWord
to all other possible words in wordList
, and second, using Depth-First Search (DFS) to reconstruct all the paths from endWord
back to beginWord
that match the shortest distance tracked by BFS.
Here's the step-by-step thought process:
-
BFS to find the shortest distance: The solution initializes a queue with
beginWord
and uses BFS to expand outwards to all possible transformations. While doing this, the solution tracks two key pieces of information: the distance (dist
) frombeginWord
to each word encountered, and a mapping (prev
) from each word to its possible precursors in the sequence. Using BFS ensures that we encounter the shortest path to each word first, and therefore when we reachendWord
, we have found the shortest distance to it. -
Tracking predecessor words: As the BFS proceeds, for each word encountered that is a possible next step from the current word, we track its predecessors - these are words one step closer to
beginWord
. We only store the predecessors that are part of the shortest path, effectively discarding longer paths. -
DFS to reconstruct paths: Once BFS finishes and if
endWord
has been reached, we use DFS starting fromendWord
to traverse back through theprev
mapping, constructing all possible shortest paths tobeginWord
. Recursive DFS is used because it allows to backtrack (remove the last added word) when a path is fully constructed, which helps to navigate to other potential paths with shared intermediate words. -
Complete the transformation sequences: The paths constructed from
endWord
tobeginWord
are reversed before being added to the final answer list to match the required format (beginWord
toendWord
).
Through this blend of BFS and DFS, we can efficiently track all the shortest transformation sequences that meet the criteria of the problem.
Learn more about Breadth-First Search and Backtracking patterns.
Solution Approach
The solution follows a two-phase approach: first, it uses Breadth-First Search (BFS) to swiftly find the shortest path lengths from beginWord
to endWord
and all intermediate words, and subsequently, Depth-First Search (DFS) is applied to backtrack and assemble all the shortest transformation sequences. Let's delve into how the solution implements this methodologically:
BFS (Breadth-First Search)
- Queue Initialization: We begin with a queue (
q
) initialized with thebeginWord
. - Distance and Predecessor Tracking: Two dictionaries are used -
dist
holds the number of steps from thebeginWord
to the current word, andprev
maintains a set of all possible preceding words for each word encountered. - Word Processing: As long as there are words in the queue and the endWord has not been found, the algorithm processes each word by:
- Popping the current word from the queue.
- Generating all possible single-letter transformations of the current word.
- For each valid transformation that is either in the
wordList
or previously encountered at the same BFS level (indicating the shortest path to that word):- Add the current word to the
prev
set of the transformed word. - If the transformed word is
endWord
, mark thatendWord
is found. - If it's a new word not seen before at a closer level, add it to the queue with an incremented distance value.
- Add the current word to the
- Termination: Once the
endWord
is found or the queue is exhausted, BFS terminates.
DFS (Depth-First Search)
- Path Reconstruction: Starting with
endWord
, the algorithm uses DFS in a recursive manner to rebuild all possible paths that lead to it frombeginWord
, given the information in theprev
dictionary. - DFS Function: A helper function
dfs
is defined for the purpose of traversing theprev
map. It:- Adds the current word to the path.
- If the current word is the
beginWord
, it means a complete path has been found, so it is reversed and added to the results. - If not, the function calls itself recursively for each predecessor of the current word (each possible previous step in the sequence).
- After each recursive call, the last word is removed from the path (backtracking), allowing for exploration of alternative paths.
Efficiency
The design of the solution ensures efficiency by:
- Using BFS for Level-by-Level Exploration: By expanding the search level by level, we first reach
endWord
at its shortest possible path because BFS explores the closest nodes first. - Storing Predecessor Words: This avoids the need to compute all transformations again during the DFS phase, as we can directly access all valid previous words.
- Pruning Non-Shortest Paths: By removing words from the
wordList
once they are visited at the current level, the algorithm eliminates any longer paths that might be visited in the future.
Execution
The algorithms and data structures work hand in hand like cogs in a complex machine, with BFS setting the groundwork by identifying all shortest distances and predecessors, and DFS taking up the final stretch by piecing together the information into complete paths. This interplay allows the solution to compile all shortest transformation sequences as per the problem's requirements.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach described above.
Suppose we have the following inputs:
- beginWord:
"hit"
- endWord:
"cog"
- wordList:
["hot","dot","dog","lot","log","cog"]
Now, let us walk through the BFS and DFS method to find all the shortest transformation sequences.
BFS (Breadth-First Search)
- Initialize a queue with the
beginWord
, which is"hit"
. - Create
dist
andprev
dictionaries to keep track of distances and predecessors. - Process words one by one. Starting with
"hit"
, we examine possible one-letter transformations:"hot"
. - Since
"hot"
is a valid word inwordList
, we add "hit" as its predecessor, set its distance, and enqueue it. - Now, the queue has
"hot"
. Dequeue and process it, checking its possible transformations:"dot"
,"lot"
. - Both words are valid in
wordList
and are enqueued, with "hot" as their predecessor. - This process continues, with words like "dot" leading to "dog", "lot" to "log", and so on, until "cog" is reached.
Through BFS, we find the shortest path to "cog" is 4 steps: hit -> hot -> dot -> dog -> cog
.
DFS (Depth-First Search)
- We start the DFS with
endWord
which is "cog". - From "cog", we look up its predecessors ("dog"), and recursively call DFS on "dog".
- "dog" leads us back to its predecessors ("dot"), and DFS continues with "dot".
- The process is repeated until we reach "hit", which has no predecessors.
- Each time we hit "hit", we have found a complete path, so we reverse it and add it to our results list.
Through DFS, we find the following paths:
["hit", "hot", "dot", "dog", "cog"]
["hit", "hot", "lot", "log", "cog"]
Efficiency
This example demonstrates how BFS ensures we hit the endWord
with the minimum number of steps, and DFS helps us reconstruct all paths that follow this shortest distance.
Execution
Putting both phases together, the solution collects all the shortest transformation sequences from beginWord
to endWord
using the provided wordList
. With this method, the problem is solved efficiently and the paths provided represent all the shortest ways to transform the starting word into the ending word using the given dictionary of words.
Solution Implementation
1from collections import deque, defaultdict
2from typing import List
3
4class Solution:
5 def findLadders(self, begin_word: str, end_word: str, word_list: List[str]) -> List[List[str]]:
6 # Helper function to perform depth-first search to find paths
7 def dfs(path: List[str], current_word: str):
8 if current_word == begin_word:
9 # Reverse the path since we are moving from endWord to beginWord
10 ans.append(path[::-1])
11 return
12 # Iterate over all predecessors and continue building the path
13 for precursor_word in predecessors[current_word]:
14 path.append(precursor_word)
15 dfs(path, precursor_word) # Recursive DFS call
16 path.pop() # Remove the last word to backtrack
17
18 ans = [] # List to store all the shortest transformation sequences
19 words = set(word_list) # Convert the word list to a set for O(1) look-ups
20
21 # Early exit if end word is not in the word list
22 if end_word not in words:
23 return ans
24
25 words.discard(begin_word) # Remove the begin word from the set of words
26 distance_from_begin = {begin_word: 0} # Dictionary to store distance of words from beginWord
27 predecessors = defaultdict(set) # Dictionary to store predecessors of each word
28
29 # Initialize queue for BFS
30 queue = deque([begin_word])
31 found = False
32 step = 0 # Number of steps taken
33
34 # Perform BFS until the queue is empty or the end word is found
35 while queue and not found:
36 step += 1
37 for _ in range(len(queue)):
38 current_word = queue.popleft()
39 word_chars = list(current_word)
40
41 # Try changing each character in the current word
42 for char_index in range(len(word_chars)):
43 original_char = word_chars[char_index]
44
45 # Try all possible transformations by changing the character to 'a' to 'z'
46 for letter in range(26):
47 word_chars[char_index] = chr(ord('a') + letter)
48 new_word = ''.join(word_chars)
49
50 # Skip words that are not one step away
51 if distance_from_begin.get(new_word, 0) == step:
52 predecessors[new_word].add(current_word)
53
54 # If the new word is in the words set, it is a valid transformation
55 if new_word in words:
56 # Add the current word as a predecessor of the new word
57 predecessors[new_word].add(current_word)
58 words.discard(new_word) # Mark the new word as visited
59 queue.append(new_word) # Add the new word to the queue
60
61 # Set the distance for the new word
62 distance_from_begin[new_word] = step
63
64 # If the end word is reached, mark that we found a transformation
65 if end_word == new_word:
66 found = True
67 # Restore the original character at the index
68 word_chars[char_index] = original_char
69
70 # If a transformation was found, reconstruct paths using DFS
71 if found:
72 dfs([end_word], end_word) # Initial call to dfs to start path reconstruction
73
74 return ans # Return the list of all shortest transformation sequences
75
1class Solution {
2 private List<List<String>> allPaths; // List of paths from beginWord to endWord
3 private Map<String, Set<String>> predecessorsMap; // Map to track the predecessors of each word in the shortest paths
4
5 public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
6 allPaths = new ArrayList<>();
7 Set<String> wordSet = new HashSet<>(wordList); // Convert word list to a set for efficient lookups
8 if (!wordSet.contains(endWord)) {
9 return allPaths; // If endWord is not in the word list, return empty list
10 }
11 wordSet.remove(beginWord); // Remove beginWord from the set to prevent cycles
12 Map<String, Integer> distanceMap = new HashMap<>(); // Map to track the shortest path distances for words
13 distanceMap.put(beginWord, 0); // Distance from beginWord to itself is 0
14 predecessorsMap = new HashMap<>(); // Initialize the predecessors map
15 Queue<String> queue = new ArrayDeque<>(); // Queue for BFS
16 queue.offer(beginWord);
17 boolean isEndWordFound = false; // Flag to check if endWord is found
18 int steps = 0; // Step counter for BFS
19 while (!queue.isEmpty() && !isEndWordFound) {
20 ++steps;
21 for (int i = queue.size(); i > 0; --i) {
22 String currentWord = queue.poll();
23 char[] currentChars = currentWord.toCharArray();
24 for (int j = 0; j < currentChars.length; ++j) {
25 char originalChar = currentChars[j];
26 for (char c = 'a'; c <= 'z'; ++c) { // Try all possible one-letter mutations
27 currentChars[j] = c;
28 String newWord = new String(currentChars);
29 if (distanceMap.getOrDefault(newWord, 0) == steps) {
30 predecessorsMap.get(newWord).add(currentWord);
31 }
32 if (!wordSet.contains(newWord)) {
33 continue; // If the new word isn't in the set, skip it
34 }
35 // Update distance map and predecessors map for new words
36 predecessorsMap.computeIfAbsent(newWord, key -> new HashSet<>()).add(currentWord);
37 wordSet.remove(newWord); // Remove new word to prevent revisiting
38 queue.offer(newWord);
39 distanceMap.put(newWord, steps);
40 if (endWord.equals(newWord)) {
41 isEndWordFound = true; // Found the endWord; will finish after this level
42 }
43 }
44 currentChars[j] = originalChar; // Restore original character before next iteration
45 }
46 }
47 }
48 if (isEndWordFound) { // If the end word has been reached
49 Deque<String> path = new ArrayDeque<>(); // Path stack for reconstructing paths
50 path.add(endWord);
51 backtrackPath(path, beginWord, endWord); // Perform DFS to build all shortest paths
52 }
53 return allPaths; // Return the list of all shortest paths
54 }
55
56 private void backtrackPath(Deque<String> path, String beginWord, String currentWord) {
57 if (currentWord.equals(beginWord)) { // If the beginning of the path is reached, add it to allPaths
58 allPaths.add(new ArrayList<>(path));
59 return;
60 }
61 // Recursively go through all predecessors of the current word, adding them to the path
62 for (String predecessor : predecessorsMap.get(currentWord)) {
63 path.addFirst(predecessor); // Push the predecessor onto the path
64 backtrackPath(path, beginWord, predecessor); // Continue backtracking
65 path.removeFirst(); // Remove the predecessor to backtrack
66 }
67 }
68}
69
1#include <vector>
2#include <unordered_set>
3#include <unordered_map>
4#include <queue>
5#include <string>
6#include <list>
7#include <algorithm>
8
9using namespace std;
10
11class Solution {
12private:
13 vector<vector<string>> allPaths; // List of paths from beginWord to endWord
14 unordered_map<string, unordered_set<string>> predecessorsMap; // Map to track the predecessors of each word in the shortest paths
15
16public:
17 vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
18 allPaths.clear();
19 unordered_set<string> wordSet(wordList.begin(), wordList.end()); // Convert word list to a set for efficient lookups
20 if (wordSet.find(endWord) == wordSet.end()) {
21 return allPaths; // If endWord is not in the word set, return empty list
22 }
23
24 wordSet.erase(beginWord); // Remove beginWord from the set to prevent cycles
25 unordered_map<string, int> distanceMap; // Map to track the shortest path distances for words
26 distanceMap[beginWord] = 0; // Distance from beginWord to itself is 0
27 predecessorsMap.clear(); // Initialize the predecessors map
28 queue<string> queue; // Queue for BFS
29 queue.push(beginWord);
30 bool isEndWordFound = false; // Flag to check if endWord is found
31 int steps = 0; // Step counter for BFS
32
33 while (!queue.empty() && !isEndWordFound) {
34 ++steps;
35 int levelSize = queue.size();
36 for (int i = 0; i < levelSize; ++i) {
37 string currentWord = queue.front();
38 queue.pop();
39 string originalWord = currentWord;
40
41 for (int j = 0; j < currentWord.size(); ++j) {
42 char originalChar = currentWord[j];
43 for (char c = 'a'; c <= 'z'; ++c) { // Try all possible one-letter mutations
44 currentWord[j] = c;
45 if (distanceMap.find(currentWord) != distanceMap.end() && distanceMap[currentWord] == steps) {
46 predecessorsMap[currentWord].insert(originalWord);
47 }
48 if (wordSet.find(currentWord) == wordSet.end()) {
49 continue; // If the new word isn't in the set, skip it
50 }
51 // Update distance map and predecessors map for new words
52 predecessorsMap[currentWord].insert(originalWord);
53 wordSet.erase(currentWord); // Remove new word to prevent revisiting
54 queue.push(currentWord);
55 distanceMap[currentWord] = steps;
56
57 if (endWord == currentWord) {
58 isEndWordFound = true; // Found the endWord; will finish after this level
59 }
60 }
61 currentWord[j] = originalChar; // Restore original character before next iteration
62 }
63 }
64 }
65
66 if (isEndWordFound) { // If the end word has been reached
67 deque<string> path; // Path stack for reconstructing paths
68 path.push_back(endWord);
69 backtrackPath(path, beginWord, endWord); // Perform DFS to build all shortest paths
70 }
71
72 return allPaths; // Return the list of all shortest paths
73 }
74
75private:
76 void backtrackPath(deque<string> path, const string& beginWord, const string& currentWord) {
77 if (currentWord == beginWord) { // If the beginning of the path is reached, add it to allPaths
78 allPaths.push_back(vector<string>(path.begin(), path.end()));
79 return;
80 }
81
82 // Recursively go through all predecessors of the current word, adding them to the path
83 for (const auto& predecessor : predecessorsMap[currentWord]) {
84 path.push_front(predecessor); // Push the predecessor onto the path
85 backtrackPath(path, beginWord, predecessor); // Continue backtracking
86 path.pop_front(); // Remove the predecessor to backtrack
87 }
88 }
89};
90
1// A global list of paths from beginWord to endWord
2let allPaths: string[][] = [];
3
4// A global map to track the predecessors of each word in the shortest paths
5let predecessorsMap: Map<string, Set<string>> = new Map();
6
7// Function to find all the shortest transformation sequences from begin word to end word
8function findLadders(beginWord: string, endWord: string, wordList: string[]): string[][] {
9 allPaths = [];
10 const wordSet: Set<string> = new Set(wordList);
11
12 // If endWord is not in the word list, return an empty list of paths
13 if (!wordSet.has(endWord)) {
14 return allPaths;
15 }
16
17 wordSet.delete(beginWord); // Remove beginWord to avoid cycles
18
19 // Map to track the shortest path distances for words from the beginWord
20 const distanceMap: Map<string, number> = new Map();
21 distanceMap.set(beginWord, 0);
22
23 predecessorsMap = new Map(); // Initialize the predecessor map
24
25 // Queue for performing BFS
26 const queue: string[] = [beginWord];
27
28 // Flag to check if the endWord was found
29 let isEndWordFound: boolean = false;
30
31 // Step counter for BFS
32 let steps: number = 0;
33
34 while (queue.length > 0 && !isEndWordFound) {
35 steps++;
36 for (let i = queue.length; i > 0; --i) {
37 const currentWord: string = <string>queue.shift();
38 const currentChars: string[] = [...currentWord];
39
40 for (let j = 0; j < currentChars.length; ++j) {
41 const originalChar: string = currentChars[j];
42
43 // Try all possible one-letter mutations
44 for (let c = 'a'.charCodeAt(0); c <= 'z'.charCodeAt(0); ++c) {
45 currentChars[j] = String.fromCharCode(c);
46 const newWord: string = currentChars.join('');
47
48 if (distanceMap.get(newWord) === steps) {
49 predecessorsMap.get(newWord)?.add(currentWord);
50 }
51
52 if (!wordSet.has(newWord)) {
53 continue; // Skip if the new word isn't in the set
54 }
55
56 // Update distance map and predecessors map for new words found
57 if (!predecessorsMap.has(newWord)) {
58 predecessorsMap.set(newWord, new Set());
59 }
60 predecessorsMap.get(newWord)?.add(currentWord);
61
62 wordSet.delete(newWord); // Remove to prevent revisiting
63 queue.push(newWord);
64 distanceMap.set(newWord, steps);
65
66 if (endWord === newWord) {
67 // Found the endWord; will finish after this level
68 isEndWordFound = true;
69 }
70 }
71 currentChars[j] = originalChar; // Restore original character before next modification
72 }
73 }
74 }
75
76 // If the end word has been reached, construct all shortest paths
77 if (isEndWordFound) {
78 let path: string[] = [endWord]; // Path stack for reconstructing paths
79 backtrackPath(path, beginWord, endWord);
80 }
81 return allPaths;
82}
83
84// Helper function to perform DFS and build all shortest transformation paths
85function backtrackPath(path: string[], beginWord: string, currentWord: string) {
86 if (currentWord === beginWord) {
87 // If the beginning of the path is reached, add the path to allPaths
88 allPaths.push([...path].reverse()); // Reverse before adding as we construct path from end to start
89 return;
90 }
91
92 // Recursively go through all predecessors of the current word
93 const predecessors: Set<string> | undefined = predecessorsMap.get(currentWord);
94 if (predecessors) {
95 for (const predecessor of predecessors) {
96 path.push(predecessor); // Push the predecessor onto the path
97 backtrackPath(path, beginWord, predecessor);
98 path.pop(); // Remove the predecessor to backtrack for the next path
99 }
100 }
101}
102
Time and Space Complexity
Time Complexity
The algorithm performs a breadth-first search (BFS) to find the shortest path from beginWord
to endWord
, while also recording all predecessors of each word along the way. In the worst-case scenario, every word in the word list can be connected to every other word, leading to a complete graph-like structure. BFS in this case would have a time complexity of O(V + E)
, where V
is the number of vertices (words) and E
is the number of edges (possible transformations). For each word, there are L
possible single-letter changes, and each change has 26 possible outcomes (the alphabet size), so the total number of edges would be O(26 * L * V)
. The time complexity can be further broken down as follows:
- BFS to find the shortest paths and record predecessors:
O(L * 26 * V)
, whereL
is the length of each word, andV
is the number of words in the word list. - Depth-first search (DFS) to reconstruct paths: In the worst case, all paths from
beginWord
toendWord
will need to be found. If there areP
such shortest paths and the depth of the search isD
(corresponding to the number of transformations needed), this operation isO(P*D)
.
Overall, the time complexity of this algorithm would be O(L * 26 * V + P * D)
.
Space Complexity
The space complexity is primarily governed by the storage of words, the queue used in BFS, and the recursive stack for DFS.
- Words storage: O(V), where
V
is the size of thewordList
. - BFS Queue: O(V), the queue could at most contain all the words.
- BFS
prev
map anddist
map: These maps will store at mostO(V)
entries if every word is encountered. - DFS Paths: Up to
O(P * D)
space may be needed to store allP
paths, each with a depth of maximumD
.
Thus, the total space complexity is O(V + P * D)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.