Word Ladder - II (Shortest Paths)

1. Problem Overview & Status Quo

In Word Ladder - I, the goal was to find the length of the shortest transformation sequence from a beginWord to an endWord using a given wordList. In Word Ladder - II, the objective is more demanding: you must return all possible shortest transformation sequences from the start word to the target word.

While a standard Breadth-First Search (BFS) works well for finding the shortest path length in Word Ladder - I, it falls short when tracking multiple paths of identical shortest lengths. If you delete words from the wordList immediately upon visiting them (the standard visited-set optimization in BFS), you might inadvertently block alternative valid paths that happen to converge on the same word at the same level.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: The Maze of Multi-Path Levels

Imagine navigating a multi-story building where you can only move room-to-room by changing a single letter of a room's label.

• You start at the ground floor (Level 0 / 1).
• At each step upward, you try all possible single-character mutations.
• Multiple staircases (sequences) can lead to the exact same room on the 3rd floor in the exact same number of steps.
• If the first person to reach a room on the 3rd floor padlocks the door (deletes the word instantly), anyone arriving via a different path a few seconds later will find the door locked and miss out on an equally short alternative route.
• The Rule: Keep the doors open until the entire floor (level) is fully processed. Only at the end of the level do you lock (delete) the rooms visited during that level so that subsequent levels cannot reuse them and lengthen the path.

3. Visualizing the BFS Level Traversal and Sequence Growth

Below is how sequences branch and grow level by level without prematurely deleting shared nodes:

4. Why Standard BFS Deletion Fails Here

In a normal graph BFS, the moment we visit a node, we mark it as visited (or remove it from a hash set) to prevent cycles and redundant visits.

In Word Ladder - II:

1. Shared Intermediate Nodes: Two different paths of the same shortest length might need the same intermediate word at the same level (e.g., both bat -> pat -> pot and bat -> bot -> pot lead to pot at Level 3).
2. Delayed Deletion Strategy: We must accumulate all transformations generated at the current level, and only delete them after the entire level is fully processed. This ensures sibling nodes in the queue can access the same valid words if they belong to separate valid shortest paths.

5. Step-by-Step Algorithm Evolution

1. Initialize Data Structures:

   • Place all words from wordList into an unordered_set for $O(1)$ lookups.
   • Initialize a Queue (queue<vector<string>>) to store active sequences. Push the initial sequence [beginWord] into the queue.
   • Maintain a tracking list (usedOnLevel) to record words used during the current BFS level.
   • Maintain an answer list of lists (vector<vector<string>>) to collect all shortest paths.

2. Queue Processing & Level Transitions:

   • Pop the front sequence from the queue.
   • Check if we have transitioned to a new BFS level. If the current sequence size exceeds the previous level threshold, bulk-erase all words stored in usedOnLevel from the master word set.
   • Extract the last word of the current sequence.

3. Character Mutation (Transformation Phase):

   • For every character position in the word (from index 0 to word.length() - 1):
     • Save the original character.
     • Iterate through alphabet characters 'a' to 'z'.
     • Form a new mutated word.
     • Check if the mutated word exists in the word set.

4. Handling Matches & Sequence Extension:

   • If the mutated word is valid, append it to a copy of the current sequence.
   • Push the new sequence into the queue.
   • Record the mutated word in usedOnLevel so it can be cleaned up at the end of the level.
   • Crucial C++ / Java Trick: Immediately pop or backtrack the added word from the sequence copy so the loop can generate the next mutation correctly without accumulating extraneous trailing elements.

6. Complete Code Implementation

Below is the complete C++ implementation demonstrating the delayed-deletion BFS strategy:

#include <vector>
#include <string>
#include <queue>
#include <unordered_set>

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        // Store words in a set for O(1) lookup
        unordered_set<string> st(wordList.begin(), wordList.end());
        
        // Queue stores sequences (paths) of words
        queue<vector<string>> q;
        q.push({beginWord});
        
        // Track words used in the current level to erase them later
        vector<string> usedOnLevel;
        int level = 0;
        
        vector<vector<string>> ans;
        
        while (!q.empty()) {
            vector<string> vec = q.front();
            q.pop();
            
            // Check if we entered a new level
            if (vec.size() > level) {
                level = vec.size();
                // Erase all words used in the previous level from the word set
                for (auto& it : usedOnLevel) {
                    st.erase(it);
                }
                usedOnLevel.clear();
            }
            
            string word = vec.back();
            
            // If we reached the end word, store the sequence
            if (word == endWord) {
                // If this is our first answer, or if it matches the shortest length found so far
                if (ans.size() == 0 || ans[0].size() == vec.size()) {
                    ans.push_back(vec);
                }
            }
            
            // Try mutating each character from 'a' to 'z'
            for (int i = 0; i < word.size(); i++) {
                char originalChar = word[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    word[i] = c;
                    
                    // If the transformed word exists in our word set
                    if (st.count(word) > 0) {
                        vec.push_back(word);
                        q.push(vec);       // Push the extended sequence into queue
                        usedOnLevel.push_back(word); // Mark as used for this level
                        vec.pop_back();    // Backtrack for the next iteration
                    }
                }
                word[i] = originalChar; // Restore original character
            }
        }
        return ans;
    }
};

7. Real-World Practical Pitfalls & Interview Context

• Time Limit Exceeded (TLE) on Platforms like LeetCode:
  • Industry Reality: Standard BFS generation of all paths in Word Ladder - II can be extremely memory- and time-intensive. Modern test cases on platforms like LeetCode have extremely strict time limits.
  • Competitive Programming (CP) vs. Interviews: Interviewers primarily test your algorithmic thinking, graph traversal logic, and ability to handle edge cases (like shared nodes across paths). The solution above is optimal for interviews. For strict online judges, competitive programmers use a two-pass approach: Backwards DFS + Memoized BFS.
• Memory Overhead: Storing full vector<string> sequences inside a queue consumes substantial memory when branching factors are large. Be prepared to discuss memory complexity trade-offs with your interviewer.

8. Summary and Key Takeaways

• Extension of Word Ladder - I: Word Ladder - II requires returning all shortest sequences rather than just the shortest transformation length.
• Level-Order BFS Structure: The traversal naturally processes paths level by level, guaranteeing that the first time you hit the endWord, all collected sequences will be of the absolute minimum length.
• Delayed Deletion Concept: Never delete or mark a word as visited immediately upon first encounter in the current level. Multiple paths at the same level may require the exact same target node.
• Batch Cleanup: Clear words from the master word set only after completing the entire current level traversal.
• Backtracking during Queue Insertion: When generating mutations, push the new sequence to the queue, record the word in the level buffer, and pop it back immediately to keep the working vector clean for subsequent character mutations.
• Interview vs. CP Distinction: This BFS + level-tracking approach is clean, intuitive, and interview-ready, though extreme competitive programming constraints may demand back-tracing optimizations.