import java.util.*;

class Solution {
    private List<List<String>> res;
    private List<List<Integer>> prev;
    private List<String> wordList;
    private String beginWord;

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        res = new ArrayList<>();
        prev = new ArrayList<>();
        this.wordList = wordList;
        this.beginWord = beginWord;
        int[] dist = new int[wordList.size()];
        boolean[] used = new boolean[wordList.size()];
        int endIdx = -1;
        List<Integer> queue = new ArrayList<>();
        for (int i = 0; i < wordList.size(); i++) {
            prev.add(new ArrayList<>());
            String word = wordList.get(i);
            if (word.equals(endWord)) endIdx = i;
            if (isConvertible(beginWord, word)) {
                used[i] = true;
                prev.get(i).add(-1);
                dist[i] = 1;
                queue.add(i);
            }
        }
        if (endIdx == -1) return res;
        while (!queue.isEmpty()) {
            List<Integer> newQueue = new ArrayList<>();
            for (Integer i : queue) {
                for (int j = 0; j < wordList.size(); j++) {
                    if (used[j]) continue;
                    if (!isConvertible(wordList.get(i), wordList.get(j))) continue;
                    prev.get(j).add(i);
                    if (dist[j] != 0) continue;
                    dist[j] = dist[i] + 1;
                    newQueue.add(j);
                }
            }
            queue = newQueue;
            for (Integer i : queue) used[i] = true;
        }
        dfs(endIdx, new LinkedList<String>());
        return res;
    }

    private void dfs(int idx, LinkedList<String> path) {
        List<String> newPath = new ArrayList<>();
        if (idx == -1) {
            newPath.add(beginWord);
            newPath.addAll(path);
            res.add(newPath);
            return;
        }
        path.addFirst(wordList.get(idx));
        for (Integer i : prev.get(idx)) {
            dfs(i, path);
        }
        path.pollFirst();
    }

    private boolean isConvertible(String w1, String w2) {
        int cnt = 0;
        for (int i = 0; i < w1.length(); i++) {
            if (w1.charAt(i) != w2.charAt(i)) cnt++;
        }
        return cnt == 1;
    }
}