MANG Problem #28: Word Ladder II (Hard)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord.

Each sequence should be a list of words [beginWord, s1, s2, ..., sk] where every adjacent pair differs by one letter.

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

2. Approach: BFS (Distances) + DFS (Backtracking)

The core challenge is finding all shortest paths, not just one.

BFS for Distance: Perform a BFS starting from beginWord to calculate the shortest distance from the source to every word in the dictionary. Store this in a Map<String, Integer> distanceMap.
Backtracking for Paths: Start from endWord (or beginWord) and use the distanceMap to guide your search.
- If you are at word W with distance D, only move to neighbors whose distance is D - 1.
- This ensures every path you find is guaranteed to be a shortest path.

3. Java Implementation

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    List<List<String>> res = new ArrayList<>();
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(endWord)) return res;
    
    Map<String, Integer> distances = new HashMap<>();
    Map<String, List<String>> adj = new HashMap<>();
    
    // 1. BFS to find minimum distances and build adjacency graph
    bfs(beginWord, endWord, dict, distances, adj);
    
    // 2. DFS to reconstruct paths
    List<String> path = new ArrayList<>();
    path.add(beginWord);
    dfs(beginWord, endWord, distances, adj, path, res);
    
    return res;
}

private void bfs(String start, String end, Set<String> dict, 
                 Map<String, Integer> dist, Map<String, List<String>> adj) {
    Queue<String> q = new LinkedList<>();
    q.offer(start);
    dist.put(start, 0);
    
    for (String s : dict) adj.put(s, new ArrayList<>());
    adj.put(start, new ArrayList<>());

    boolean found = false;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            String curr = q.poll();
            int d = dist.get(curr);
            
            List<String> neighbors = getNeighbors(curr, dict);
            for (String n : neighbors) {
                adj.get(curr).add(n);
                if (!dist.containsKey(n)) {
                    dist.put(n, d + 1);
                    if (n.equals(end)) found = true;
                    else q.offer(n);
                }
            }
        }
        if (found) break;
    }
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: Word Ladder I is about finding a number. Word Ladder II is about Tracing the Map. You cannot find the paths in the BFS pass alone without consuming massive memory.
The Guide: The distanceMap is your GPS. It tells you exactly which way to go at every crossroads to stay on the shortest path.
The Reverse: Why backtrack? Because it prunes all dead ends. Every step you take using the distanceMap is guaranteed to lead closer to the destination.

5. Interview Discussion

Interviewer: "Why is this harder than Word Ladder I?"
You: "In I, we just return the level. In II, we must explore all branches of the same level. If 'hot' and 'dot' both lead to 'dog' in the same number of steps, we need to record both."
Interviewer: "Complexity?"
You: "The time complexity is dominated by the number of possible shortest paths, which can be exponential in the worst case. The BFS part is $O(N \times L^2)$."

5. Verbal Interview Script (Staff Tier)

Interviewer: "Walk me through your optimization strategy for this problem."

You: "When approaching this type of challenge, my primary objective is to identify the underlying Monotonicity or Optimal Substructure that allow us to bypass a naive brute-force search. In my implementation of 'MANG Problem #28: Word Ladder II (Hard)', I focused on reducing the time complexity by leveraging a HashMap-based lookup. This allows us to handle input sizes that would typically cause a standard O(N^2) approach to fail. Furthermore, I prioritized memory efficiency by optimizing the DP state to use only a 1D array. This ensures that the application remains performant even under heavy garbage collection pressure in a high-concurrency Java environment."

6. Staff-Level Interview Follow-Ups

Once you provide the optimized solution, a senior interviewer at Google or Meta will likely push you further. Here is how to handle the most common follow-ups:

Follow-up 1: "How does this scale to a Distributed System?"

If the input data is too large to fit on a single machine (e.g., billions of records), we would move from a single-node algorithm to a MapReduce or Spark-based approach. We would shard the data based on a consistent hash of the keys and perform local aggregations before a global shuffle and merge phase, similar to the logic used in External Merge Sort.

Follow-up 2: "What are the Concurrency implications?"

In a multi-threaded Java environment, we must ensure that our state (e.g., the DP table or the frequency map) is thread-safe. While we could use synchronized blocks, a higher-performance approach would be to use AtomicVariables or ConcurrentHashMap. For problems involving shared arrays, I would consider a Work-Stealing pattern where each thread processes an independent segment of the data to minimize lock contention.

7. Performance Nuances (The Java Perspective)

Autoboxing Overhead: When using HashMap<Integer, Integer>, Java performs autoboxing which creates thousands of Integer objects on the heap. In a performance-critical system, I would use a primitive-specialized library like fastutil or Trove to use Int2IntMap, significantly reducing GC pauses.
Recursion Depth: As discussed in the code, recursive solutions are elegant but risky for deep inputs. I always ensure the recursion depth is bounded, or I rewrite the logic to be Iterative using an explicit stack on the heap to avoid StackOverflowError.

Key Takeaways

If you are at word W with distance D, only move to neighbors whose distance is D - 1.
This ensures every path you find is guaranteed to be a shortest path.
Interviewer: "Why is this harder than Word Ladder I?"