126. Word Ladder II

HardBreadth-First SearchHash TableStringBacktracking
Leetcode Link

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.

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:

  1. 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) from beginWord 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 reach endWord, we have found the shortest distance to it.

  2. 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.

  3. DFS to reconstruct paths: Once BFS finishes and if endWord has been reached, we use DFS starting from endWord to traverse back through the prev mapping, constructing all possible shortest paths to beginWord. 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.

  4. Complete the transformation sequences: The paths constructed from endWord to beginWord are reversed before being added to the final answer list to match the required format (beginWord to endWord).

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

In a binary min heap, the minimum element can be found in:

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 the beginWord.
  • Distance and Predecessor Tracking: Two dictionaries are used - dist holds the number of steps from the beginWord to the current word, and prev 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 that endWord 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.
  • 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 from beginWord, given the information in the prev dictionary.
  • DFS Function: A helper function dfs is defined for the purpose of traversing the prev 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example 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)

  1. Initialize a queue with the beginWord, which is "hit".
  2. Create dist and prev dictionaries to keep track of distances and predecessors.
  3. Process words one by one. Starting with "hit", we examine possible one-letter transformations: "hot".
  4. Since "hot" is a valid word in wordList, we add "hit" as its predecessor, set its distance, and enqueue it.
  5. Now, the queue has "hot". Dequeue and process it, checking its possible transformations: "dot", "lot".
  6. Both words are valid in wordList and are enqueued, with "hot" as their predecessor.
  7. 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)

  1. We start the DFS with endWord which is "cog".
  2. From "cog", we look up its predecessors ("dog"), and recursively call DFS on "dog".
  3. "dog" leads us back to its predecessors ("dot"), and DFS continues with "dot".
  4. The process is repeated until we reach "hit", which has no predecessors.
  5. 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
Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

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), where L is the length of each word, and V is the number of words in the word list.
  • Depth-first search (DFS) to reconstruct paths: In the worst case, all paths from beginWord to endWord will need to be found. If there are P such shortest paths and the depth of the search is D (corresponding to the number of transformations needed), this operation is O(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 the wordList.
  • BFS Queue: O(V), the queue could at most contain all the words.
  • BFS prev map and dist map: These maps will store at most O(V) entries if every word is encountered.
  • DFS Paths: Up to O(P * D) space may be needed to store all P paths, each with a depth of maximum D.

Thus, the total space complexity is O(V + P * D).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Recommended Readings

BFS Fundamentals

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 1

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫