Log inSign up
hardLeetCodeNot Started

Word Ladder II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that: - Every adjacent pair of words differs by a single letter. - Every si for 1 <= i <= k is in wordList. - sk == endWord.

Given two words, beginWord and endWord, and a dictionary wordList, return *all the shortest transformation sequences from beginWord to endWord*. You may return the answers in any order.

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
  • All the words in wordList are meaningful and unique.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Construct all shortest paths using a two-pass BFS (Level Graph) + DFS (Path Reconstruction) paradigm.
  • Prevent Memory Limit Exceeded (MLE) by avoiding path cloning in BFS queues.
  • Maintain multiple valid predecessors for nodes with equal shortest paths.
  • Backtrack efficiently from target to source on the condensed level DAG.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever a problem asks for 'all shortest paths' in an unweighted graph, do NOT clone paths in the BFS queue. Instead, use BFS to build the shortest distance / parent graph, then use DFS backtracking on the DAG to reconstruct all paths.

1. BFS Storing Full Paths in Queue

Intuition

Store entire paths in the BFS queue: queue<vector<string>>. On each level, collect words used in paths so they are not reused in deeper levels. Terminate when paths reaching endWord are found. While simple, copying vector paths at every step incurs significant memory and time overhead.

Algorithm

  1. Initialize queue of paths with [[beginWord]].
  2. Store dictionary in a set.
  3. Keep track of words visited on the current level to remove them from dictionary after the level finishes.
  4. While queue is not empty and no paths reached endWord:
  5. For each path in queue:
  6. Mutate last word to find valid next words in dictionary.
  7. Create new path [...path, nextWord] and push to next level queue.
  8. Collect all paths ending in endWord.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <queue>
6
7std::vector<std::vector<std::string>> findLaddersBFSQueue(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
8 std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
9 if (dict.find(endWord) == dict.end()) return {};
10
11 std::queue<std::vector<std::string>> q;
12 q.push({beginWord});
13
14 std::vector<std::vector<std::string>> result;
15 std::unordered_set<std::string> visitedThisLevel;
16 bool found = false;
17
18 while (!q.empty() && !found) {
19 int size = q.size();
20 visitedThisLevel.clear();
21
22 for (int k = 0; k < size; ++k) {
23 auto path = q.front();
24 q.pop();
25 std::string word = path.back();
26
27 for (int i = 0; i < (int)word.size(); ++i) {
28 char orig = word[i];
29 for (char c = 'a'; c <= 'z'; ++c) {
30 word[i] = c;
31 if (dict.find(word) != dict.end()) {
32 visitedThisLevel.insert(word);
33 auto newPath = path;
34 newPath.push_back(word);
35 if (word == endWord) {
36 result.push_back(newPath);
37 found = true;
38 } else {
39 q.push(newPath);
40 }
41 }
42 }
43 word[i] = orig;
44 }
45 }
46
47 for (const auto& w : visitedThisLevel) {
48 dict.erase(w);
49 }
50 }
51
52 return result;
53}
54
55int main() {
56 std::vector<std::string> words = {"hot","dot","dog","lot","log","cog"};
57 auto res = findLaddersBFSQueue("hit", "cog", words);
58 std::cout << "Shortest Ladders count: " << res.size() << std::endl;
59 for (auto& path : res) {
60 for (auto& w : path) std::cout << w << " ";
61 std::cout << std::endl;
62 }
63 return 0;
64}

Time & Space Complexity

  • Time complexity: O(N * 26^L * L) with large constants due to path vector copying.
  • Space complexity: O(N * L * (number of paths)) which causes high memory usage.

2. BFS with Forward Adjacency DAG + DFS

Intuition

Run standard BFS to record the level/depth of every reachable word. Only keep directed edges from words at level k to words at level k + 1. After BFS completes, run DFS starting from beginWord down to endWord following only forward DAG edges.

Algorithm

  1. Record distance of each word from beginWord in a hash map dist using BFS.
  2. Store valid forward transitions in an adjacency list adj (only edges where dist[v] == dist[u] + 1).
  3. If endWord was not reached, return [].
  4. Run DFS from beginWord to endWord exploring only forward edges in adj.
  5. Collect each path reaching endWord.
  6. Return all collected paths.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <unordered_map>
6#include <queue>
7
8void dfsForward(const std::string& curr, const std::string& target,
9 std::unordered_map<std::string, std::vector<std::string>>& adj,
10 std::vector<std::string>& path, std::vector<std::vector<std::string>>& results) {
11 if (curr == target) {
12 results.push_back(path);
13 return;
14 }
15 for (const auto& next : adj[curr]) {
16 path.push_back(next);
17 dfsForward(next, target, adj, path, results);
18 path.pop_back();
19 }
20}
21
22std::vector<std::vector<std::string>> findLaddersForwardDAG(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
23 std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
24 if (dict.find(endWord) == dict.end()) return {};
25
26 std::unordered_map<std::string, int> dist;
27 std::unordered_map<std::string, std::vector<std::string>> adj;
28 std::queue<std::string> q;
29
30 q.push(beginWord);
31 dist[beginWord] = 0;
32
33 while (!q.empty()) {
34 std::string word = q.front();
35 q.pop();
36
37 int d = dist[word];
38 std::string original = word;
39
40 for (int i = 0; i < (int)word.size(); ++i) {
41 char orig = word[i];
42 for (char c = 'a'; c <= 'z'; ++c) {
43 word[i] = c;
44 if (dict.find(word) != dict.end()) {
45 if (dist.find(word) == dist.end()) {
46 dist[word] = d + 1;
47 q.push(word);
48 adj[original].push_back(word);
49 } else if (dist[word] == d + 1) {
50 adj[original].push_back(word);
51 }
52 }
53 }
54 word[i] = orig;
55 }
56 }
57
58 std::vector<std::vector<std::string>> results;
59 std::vector<std::string> path = {beginWord};
60 dfsForward(beginWord, endWord, adj, path, results);
61 return results;
62}
63
64int main() {
65 std::vector<std::string> words = {"hot","dot","dog","lot","log","cog"};
66 auto res = findLaddersForwardDAG("hit", "cog", words);
67 std::cout << "Forward DAG Ladders count: " << res.size() << std::endl;
68 return 0;
69}

Time & Space Complexity

  • Time complexity: O(26 * L * N + K * L) where K is the number of shortest paths.
  • Space complexity: O(N * L) for distance map and DAG edges.

3. BFS Predecessor DAG + Backward DFS Backtracking

Intuition

Run BFS level by level. When building the DAG, store predecessors (parent[child] = [parents]). Backtracking from endWord backwards to beginWord using DFS only follows edges that lead to the source, guaranteeing that zero redundant branches are ever explored. This is the optimal benchmark pattern that avoids all MLE and TLE pitfalls.

Algorithm

  1. Store dictionary in a set. If endWord not in dictionary, return [].
  2. Maintain parents map: parents[word] stores list of words that reach word in shortest steps.
  3. Maintain levels map: levels[word] stores shortest distance from beginWord.
  4. BFS queue starts with beginWord (level 0).
  5. While queue not empty and endWord not finalized:
  6. For each word in current queue level:
  7. Generate mutations.
  8. If mutant in dictionary:
  9. If mutant not in levels:
  10. levels[mutant] = currLevel + 1
  11. parents[mutant].push(currWord)
  12. queue.push(mutant)
  13. Else if levels[mutant] == currLevel + 1:
  14. parents[mutant].push(currWord)
  15. DFS backtrack from endWord to beginWord along parents.
  16. Reverse each path and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <unordered_map>
6#include <queue>
7#include <algorithm>
8
9void backtrackDFS(const std::string& word, const std::string& beginWord,
10 std::unordered_map<std::string, std::vector<std::string>>& parents,
11 std::vector<std::string>& path, std::vector<std::vector<std::string>>& results) {
12 if (word == beginWord) {
13 auto fullPath = path;
14 std::reverse(fullPath.begin(), fullPath.end());
15 results.push_back(fullPath);
16 return;
17 }
18 for (const auto& p : parents[word]) {
19 path.push_back(p);
20 backtrackDFS(p, beginWord, parents, path, results);
21 path.pop_back();
22 }
23}
24
25std::vector<std::vector<std::string>> findLadders(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
26 std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
27 if (dict.find(endWord) == dict.end()) return {};
28
29 std::unordered_map<std::string, std::vector<std::string>> parents;
30 std::unordered_map<std::string, int> levels;
31 std::queue<std::string> q;
32
33 q.push(beginWord);
34 levels[beginWord] = 0;
35
36 bool reachedEnd = false;
37
38 while (!q.empty() && !reachedEnd) {
39 int size = q.size();
40 for (int k = 0; k < size; ++k) {
41 std::string word = q.front();
42 q.pop();
43 int currLevel = levels[word];
44
45 std::string original = word;
46 for (int i = 0; i < (int)word.size(); ++i) {
47 char origChar = word[i];
48 for (char c = 'a'; c <= 'z'; ++c) {
49 word[i] = c;
50 if (dict.find(word) != dict.end()) {
51 if (levels.find(word) == levels.end()) {
52 levels[word] = currLevel + 1;
53 parents[word].push_back(original);
54 q.push(word);
55 if (word == endWord) reachedEnd = true;
56 } else if (levels[word] == currLevel + 1) {
57 parents[word].push_back(original);
58 }
59 }
60 }
61 word[i] = origChar;
62 }
63 }
64 }
65
66 std::vector<std::vector<std::string>> results;
67 if (parents.find(endWord) != parents.end()) {
68 std::vector<std::string> path = {endWord};
69 backtrackDFS(endWord, beginWord, parents, path, results);
70 }
71 return results;
72}
73
74int main() {
75 std::vector<std::string> words = {"hot","dot","dog","lot","log","cog"};
76 auto res = findLadders("hit", "cog", words);
77 std::cout << "Optimal Word Ladder II Count: " << res.size() << std::endl;
78 for (auto& path : res) {
79 for (auto& w : path) std::cout << w << " ";
80 std::cout << std::endl;
81 }
82 return 0;
83}

Time & Space Complexity

  • Time complexity: O(26 * L * N + K * L) where K is the number of shortest paths. Each word is mutated in O(26*L) time, and DFS traces only valid paths.
  • Space complexity: O(N * L) for parents map and levels map.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.BFS Storing Full PathsO(N * 26^L * L)O(Paths * L)Conceptually direct; paths are built as BFS unfolds.Causes Memory Limit Exceeded (MLE) by cloning entire path arrays at every node.
2.Forward DAG + DFSO(26*L*N + K*L)O(N * L)Separates BFS distance discovery from DFS path collection.Forward search can encounter dead ends if nodes do not lead to target.
3.Predecessor DAG + Backward DFSOptimalO(26*L*N + K*L)O(N * L)Optimal benchmark; zero dead ends because backward DFS only follows paths that successfully reached target.Paths must be reversed upon reaching beginWord.

Common Pitfalls & Crucial Edge Cases

Deleting mutant from dictionary immediately upon first encounter in BFS.

Another word on the same level might also transform into mutant, which is required for alternate shortest paths. Delete words only after the entire level finishes, or track levels via a Map.

Doing forward DFS and getting stuck in dead ends.

Backtrack backward from endWord to beginWord along the predecessor DAG.

Crucial Edge Cases to Validate:

  • endWord not in wordList — Immediately return empty array [].
  • Multiple shortest paths with identical length — Predecessors map records all equal-depth parents, ensuring DFS captures every valid path permutation.
  • beginWord connects directly to endWord in 1 step — Produces single path [[beginWord, endWord]].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the classic two-step pattern: 'BFS for distance DAG, followed by DFS backtracking for all shortest paths.'
  2. Explain why backward backtracking from endWord to beginWord is optimal (avoids exploring branches that never reach endWord).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does storing full path vectors in the BFS queue cause MLE on Word Ladder II?

2.When should a parent be added to parents[mutant] in the BFS phase?

3.What is the benefit of stopping the BFS queue loop once reachedEnd is true?

Back to DSA Sheet