---

1. Problem Summary

You are given:

• a string beginWord
• a string endWord
• a list of words wordList

Your task is to:

Return all shortest transformation sequences from beginWord to endWord, such that:

1. Only one letter can change at a time
2. Each transformed word must exist in wordList
3. The transformation must end exactly at endWord
4. Output paths must be shortest possible
5. Sequences must be in order of transformation

Example:

Input:

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

Output:

[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

---

2. Key Insights

Insight 1: This is a shortest-path problem in word graph

Each word is a node.
Edges exist between words that differ by exactly one letter.

Insight 2: BFS ensures shortest path length

We must not use DFS first, because DFS finds deeper (longer) paths.

Insight 3: We must collect all shortest paths, not just one

So we:

• run BFS to determine shortest distance to each reachable word
• then run DFS/backtracking to construct all valid shortest sequences

Insight 4: We need adjacency tracking

While BFS runs, we store mapping:

parentList[word] = list of words that can lead to it in shortest path

Insight 5: Stop BFS once endWord level discovered

No need to explore deeper levels.

---

3. Approach

Phase 1: BFS to build graph levels and parent links

Steps:

1. Convert wordList into a Set for O(1) lookup
2. Ensure endWord exists; if not, return empty result
3. Initialize:
   • queue for BFS levels
   • map for parent tracking
4. For each word dequeued:
   • generate all possible one-letter transformations
   • if valid and unvisited this level:
     • store parent relationship
     • add to next BFS level
5. Stop when endWord reached

Phase 2: Backtracking to reconstruct sequences

Steps:

1. Start from endWord
2. Recursively walk backward through parent lists
3. Build sequences until reaching beginWord
4. Reverse collected sequences before adding to final output

---

4. Time and Space Complexity

Time Complexity:

O(N * L²)

Where:

• N = number of words
• L = length of each word
  Reason:
• BFS generates neighbors by mutating each char (L options) and matching words

Space Complexity:

O(N * L)

For:

• adjacency parent mapping
• BFS frontier
• recursion stacks

---

5. Java Solution

import java.util.*;

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        List<List<String>> result = new ArrayList<>();

        if (!wordSet.contains(endWord)) {
            return result;
        }

        Map<String, List<String>> parents = new HashMap<>();
        Set<String> currentLevel = new HashSet<>();
        currentLevel.add(beginWord);

        boolean foundEnd = false;
        wordSet.remove(beginWord);

        while (!currentLevel.isEmpty() && !foundEnd) {
            Set<String> nextLevel = new HashSet<>();

            for (String word : currentLevel) {
                parents.put(word, new ArrayList<>());
            }

            for (String word : currentLevel) {
                char[] chars = word.toCharArray();

                for (int i = 0; i < chars.length; i++) {
                    char original = chars[i];

                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == original) continue;

                        chars[i] = c;
                        String newWord = String.valueOf(chars);

                        if (wordSet.contains(newWord)) {
                            nextLevel.add(newWord);
                            parents.get(newWord).add(word);

                            if (newWord.equals(endWord)) {
                                foundEnd = true;
                            }
                        }
                    }

                    chars[i] = original;
                }
            }

            wordSet.removeAll(nextLevel);
            currentLevel = nextLevel;
        }

        if (foundEnd) {
            List<String> path = new ArrayList<>();
            backtrack(result, parents, path, endWord, beginWord);
        }

        return result;
    }

    private void backtrack(List<List<String>> result,
                           Map<String, List<String>> parents,
                           List<String> path,
                           String word,
                           String beginWord) {

        path.add(word);

        if (word.equals(beginWord)) {
            List<String> validPath = new ArrayList<>(path);
            Collections.reverse(validPath);
            result.add(validPath);
        } else {
            if (parents.containsKey(word)) {
                for (String parent : parents.get(word)) {
                    backtrack(result, parents, path, parent, beginWord);
                }
            }
        }

        path.remove(path.size() - 1);
    }
}

---

6. Dry Run Examples

Example 1

Input:

hit, cog, ["hot","dot","dog","lot","log","cog"]

BFS levels:

hit
hot
dot, lot
dog, log
cog

Parent mapping leads to two valid paths.

Output:

[
 ["hit","hot","dot","dog","cog"],
 ["hit","hot","lot","log","cog"]
]

---

Example 2

Input:

beginWord = "a"
endWord   = "c"
wordList  = ["a","b","c"]

Paths:

a → c (through "c")

Output:

[["a","c"]]

---

Example 3

Input:

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

cog not present → impossible

Output:

[]

---

Example 4

Input:

["red","ted","tex","tax","tad","rad","rex"]

Multiple parallel shortest ladders.

---

Example 5

Large branching but shortest preserved due to BFS cutoff.

---

7. Why This Solution Works

• BFS guarantees minimal path length discovery
• Parent tracking preserves all shortest predecessors
• Backtracking reconstructs full path sets
• Avoids exploring deeper unnecessary paths
• Efficient pruning prevents exponential explosion

---

8. Common Mistakes

1. Using DFS first (finds non-shortest paths)
2. Modifying wordList instead of using a Set
3. Forgetting to remove visited words per level
4. Returning only one path
5. Building adjacency graph fully (too slow)