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 == endWordGiven 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 <= 5endWord.length == beginWord.length1 <= wordList.length <= 500wordList[i].length == beginWord.lengthbeginWord, endWord, and wordList[i] consist of lowercase English letters.beginWord != endWordwordList are unique.105.Word Ladder II asks you to return all shortest transformation sequences from a start word to an end word where each step changes only one character and must exist in the dictionary. The key challenge is generating all shortest paths, not just the length.
A common strategy is to combine Breadth-First Search (BFS) with backtracking. BFS explores the word graph level by level to guarantee that the first time the target word is reached corresponds to the shortest transformation depth. During BFS, you build a mapping of each word to its possible parent words from the previous level. This effectively creates a layered graph of valid transitions.
Once BFS finishes, a DFS/backtracking step reconstructs all valid paths from the end word back to the start word using the parent relationships discovered earlier. Efficient neighbor generation (by changing characters or using pattern hashing) helps keep the search manageable.
This approach ensures only shortest paths are explored while keeping the transformation graph compact.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS + Backtracking (Parent Graph) | O(N * L * 26) for BFS exploration and path reconstruction | O(N * L + P) for graph storage and paths |
take U forward
The idea is to optimize the BFS by starting the search from both the beginWord and the endWord simultaneously. This bidirectional approach helps in cutting down the search space significantly as the two searches will meet in the middle.
Initially, we create two sets to track words to visit from the beginning side and the ending side. We also use a visited set to ensure we do not revisit any words.
We alternate the search extensions from one side to another to maintain the balance of the search width for the two meet points.
Due to the bidirectional nature, the time complexity can be greatly reduced compared to a conventional BFS.
Time Complexity: O(N * M * 26) where N is the number of words and M is the word length.
Space Complexity: O(N * M) due to the storage of the graph.
1function findLadders(beginWord, endWord, wordList) {
2 const tree = new Map();
3 const wordSet = new Set(wordList);
4 if (!wordSet.has(endWord)) return [];
5 let found = false;
6 let q = new Set([beginWord]);
7 while (q.size && !found) {
8 wordSet.forEach(
9 word => q.has(word) ? wordSet.delete(word) : null
10 );
11 const nextSet = new Set();
12 for (let word of q) {
13 for (let i = 0; i < word.length; i++) {
14 for (let j = 97; j <= 122; j++) {
15 const newWord = word.slice(0, i) + String.fromCharCode(j) + word.slice(i + 1);
16 if (wordSet.has(newWord) || newWord == endWord) {
17 if (!tree.has(word)) tree.set(word, []);
18 tree.get(word).push(newWord);
19 if (newWord == endWord) found = true;
20 nextSet.add(newWord);
21 }
22 }
23 }
24 }
25 q = nextSet;
26 }
27
28 const res = [];
29 function dfs(word, path) {
30 if (word === endWord) {
31 res.push([...path, word]);
32 return;
33 }
34 if (tree.has(word)) {
35 for (let next of tree.get(word)) {
36 dfs(next, [...path, word]);
37 }
38 }
39 }
40 dfs(beginWord, []);
41 return res;
42}This JavaScript code employs a similar strategy using Sets for managing word transformations and a map to track paths during BFS. The DFS helper function then reconstructs all valid paths after the BFS concludes.
Using a single queue BFS, we explore transformations level by level. We build a graph where each word is a node, and edges are valid single-letter transformations as they appear in the word list. During BFS, paths are stored and checked for minimum length.
We mark words visited in the current level to avoid loops and unnecessary processing.
Once a complete path is found its length is compared to ensure it’s the smallest, and added to results if valid.
Time Complexity: O(N * M * 26).
Space Complexity: O(N * M).
1#include <stdio.h>
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
BFS guarantees that nodes are visited level by level, which ensures the first time you reach the target word corresponds to the shortest transformation length. This prevents exploring longer unnecessary paths.
Yes, Word Ladder II and related variations are frequently discussed in technical interviews at top companies. They test knowledge of BFS, graph modeling with strings, and path reconstruction techniques.
A hash set is commonly used to store the dictionary for fast lookups, while a hash map stores parent relationships between words during BFS. Queues are used for BFS traversal and recursion or stacks for backtracking.
The optimal approach uses Breadth-First Search to discover the shortest transformation levels and build a parent mapping for each word. After BFS finishes, backtracking or DFS is used to reconstruct all valid shortest sequences from the end word to the start word.
This C code uses a loop-based BFS leveraging basic queue operations to explore each word's path to potential matches. A helper function ensures only one-letter transformations are pursued. The transformation check and BFS implementation are in C style for maximum control over memory and data handling.