Word Ladder II

This approach uses a Breadth-First Search (BFS) to explore the word transformations level by level. To reconstruct the paths, the entire path from the beginWord to the current word is stored in the BFS queue. When a path reaches the endWord, it's added to a result list. The search continues only up to the level where the first shortest path is found to ensure all collected paths are of minimum length.

• Initialize a queue to store paths (lists of words). Add the initial path [beginWord].
• Convert wordList to a Set for efficient O(1) lookups.
• Perform a level-by-level Breadth-First Search (BFS).
• In each level, process all paths currently in the queue.
• For each path, take the last word and generate all its one-letter-different neighbors.
• If a neighbor is the endWord, a shortest path is found. Add this complete path to the results list and set a flag found to true.
• If a neighbor is a valid word in the dictionary and hasn't been visited in the current level, create a new path by appending the neighbor and add it to the queue. Keep track of these newly visited words in a visitedInLevel set.
• After a level is fully processed, if found is true, terminate the search.
• Otherwise, remove all words in visitedInLevel from the main dictionary set to prevent cycles and longer paths. Continue to the next level.

This method directly translates the problem into a pathfinding search on a graph. We treat each word as a node and a single-letter difference as an edge.

The core of this approach is a BFS, which naturally finds the shortest path in terms of the number of transformations (edges). The main challenge is to find all shortest paths. To do this, we store the entire transformation sequence (path) in our BFS queue instead of just the current word.

Here's the process:

1. We start with a queue containing a single path: [beginWord].
2. We process the search level by level. For each level, we dequeue all paths of that length.
3. For each path, we look at the last word and find all its valid neighbors (one letter difference, present in the wordList).
4. If a neighbor is the endWord, we've found a shortest path. We add the full path to our results. We make a note that we've found a solution, which means we don't need to explore any deeper levels.
5. If a neighbor is another valid word, we create a new path by extending the current one and add it to the queue for the next level's processing.
6. A crucial step for correctness and efficiency is to avoid cycles and moving backward. We do this by keeping track of all words visited at the current level. After the level is complete, we remove all these words from our dictionary set. This ensures that in subsequent (longer) paths, we don't revisit these words.

While conceptually simple, this approach is highly inefficient as the number of paths can grow exponentially, leading to excessive memory and time consumption.

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> results = new ArrayList<>();
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return results;
        }

        Queue<List<String>> queue = new LinkedList<>();
        List<String> initialPath = new ArrayList<>();
        initialPath.add(beginWord);
        queue.offer(initialPath);

        Set<String> visitedInLevel = new HashSet<>();
        visitedInLevel.add(beginWord);

        boolean found = false;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            // Words visited in the current level are removed from the main dict
            // after the level is processed to avoid cycles and longer paths.
            for (String word : visitedInLevel) {
                dict.remove(word);
            }
            visitedInLevel.clear();

            if (found) break; // Stop if shortest paths were found in the previous level

            for (int i = 0; i < levelSize; i++) {
                List<String> currentPath = queue.poll();
                String lastWord = currentPath.get(currentPath.size() - 1);

                char[] chars = lastWord.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char originalChar = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String newWord = new String(chars);

                        if (dict.contains(newWord)) {
                            List<String> newPath = new ArrayList<>(currentPath);
                            newPath.add(newWord);
                            if (newWord.equals(endWord)) {
                                results.add(newPath);
                                found = true;
                            } else {
                                visitedInLevel.add(newWord);
                                queue.offer(newPath);
                            }
                        }
                    }
                    chars[j] = originalChar; // backtrack
                }
            }
        }
        return results;
    }
}