import java.util.*;

class Solution {
    private int min;

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        int begIdx = -1, endIdx = -1;
        for (int i = 0; i < wordList.size(); i++) {
            String word = wordList.get(i);
            if (word.equals(beginWord)) begIdx = i;
            if (word.equals(endWord)) endIdx = i;
        }
        if (begIdx == -1) begIdx = wordList.size();
        if (endIdx == -1) return res;
        // Create adj matrix
        int n = Math.max(wordList.size(), begIdx + 1);
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < n; i++) {
            List<Integer> li = adj.get(i);
            String w1 = i == begIdx ? beginWord : wordList.get(i);
            for (int j = 0; j < wordList.size(); j++) {
                String w2 = wordList.get(j);
                if (isConvertible(w1, w2)) li.add(j);
            }
        }
        // Init path
        min = Integer.MAX_VALUE;
        List<String> path = new ArrayList<>();
        path.add(beginWord);
        boolean[] used = new boolean[wordList.size()];
        if (begIdx < wordList.size()) used[begIdx] = true;
        dfs(adj, wordList, res, path, used, begIdx, endIdx);
        return res;
    }

    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;
    }

    private void dfs(List<List<Integer>> adj, List<String> words, List<List<String>> res, List<String> path, boolean[] used, int idx, int endIdx) {
        if (min < path.size()) return;
        if (idx == endIdx) {
            if (path.size() < min) {
                res.clear();
                min = path.size();
            }
            List<String> copy = new ArrayList<>();
            copy.addAll(path);
            res.add(copy);
            return;
        }
        List<Integer> li = adj.get(idx);
        for (Integer next : li) {
            if (used[next]) continue;
            used[next] = true;
            path.add(words.get(next));
            dfs(adj, words, res, path, used, next, endIdx);
            used[next] = false;
            path.remove(path.size() - 1);
        }
    }
}