from collections import defaultdict, deque

class Solution:
    def findLadders(self, beginWord, endWord, wordList):
        wordSet = set(wordList)
        if endWord not in wordSet:
            return []

        # BFS to build the tree of shortest paths
        layer = {}
        layer[beginWord] = [[beginWord]]
        while layer:
            new_layer = defaultdict(list)
            for word in layer:
                if word == endWord:
                    return layer[word]
                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        new_word = word[:i] + c + word[i+1:]
                        if new_word in wordSet:
                            new_layer[new_word] += [j + [new_word] for j in layer[word]]
            wordSet -= set(new_layer.keys())
            layer = new_layer
        return []
      

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

using namespace std;

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        vector<vector<string>> res;
        if (wordSet.find(endWord) == wordSet.end()) return res;
        
        unordered_map<string, vector<vector<string>>> layer;
        layer[beginWord] = {{beginWord}};
        
        while (!layer.empty()) {
            unordered_map<string, vector<vector<string>>> new_layer;
            for (auto& item : layer) {
                string word = item.first;
                if (word == endWord) {
                    return layer[word];
                }
                for (int i = 0; i < word.size(); ++i) {
                    string newWord = word;
                    for (char c = 'a'; c <= 'z'; ++c) {
                        newWord[i] = c;
                        if (wordSet.count(newWord)) {
                            for (auto seq : item.second) {
                                seq.push_back(newWord);
                                new_layer[newWord].push_back(seq);
                            }
                        }
                    }
                }
            }
            for (auto& item : new_layer)
                wordSet.erase(item.first);
            layer = new_layer;
        }
        return {};
    }
};
      

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>> res = new ArrayList<>();
        if (!wordSet.contains(endWord)) return res;

        Map<String, List<List<String>>> layer = new HashMap<>();
        layer.put(beginWord, new ArrayList<>(Arrays.asList(Arrays.asList(beginWord))));

        while (!layer.isEmpty()) {
            Map<String, List<List<String>>> newLayer = new HashMap<>();
            for (String word : layer.keySet()) {
                if (word.equals(endWord)) {
                    return layer.get(word);
                }
                for (int i = 0; i < word.length(); i++) {
                    char[] chars = word.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[i] = c;
                        String newWord = new String(chars);
                        if (wordSet.contains(newWord)) {
                            for (List<String> seq : layer.get(word)) {
                                List<String> next = new ArrayList<>(seq);
                                next.add(newWord);
                                newLayer.computeIfAbsent(newWord, k -> new ArrayList<>()).add(next);
                            }
                        }
                    }
                }
            }
            for (String key : newLayer.keySet())
                wordSet.remove(key);
            layer = newLayer;
        }
        return res;
    }
}
      

var findLadders = function(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return [];
    let layer = {};
    layer[beginWord] = [[beginWord]];
    while (Object.keys(layer).length > 0) {
        const newLayer = {};
        for (const word in layer) {
            if (word === endWord) {
                return layer[word];
            }
            for (let i = 0; i < word.length; i++) {
                for (let c = 97; c <= 122; c++) {
                    const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
                    if (wordSet.has(newWord)) {
                        if (!newLayer[newWord]) newLayer[newWord] = [];
                        for (const seq of layer[word]) {
                            newLayer[newWord].push([...seq, newWord]);
                        }
                    }
                }
            }
        }
        for (const key in newLayer) wordSet.delete(key);
        layer = newLayer;
    }
    return [];
};