import java.util.*;

public class Solution2 {
    private List<List<String>> res = new ArrayList<>();
    private HashSet<Integer>[] G;
    private List<String> wordList;
    private int[] visitedBFS;
    private boolean[] visitedDFS;
    private String beginWord;
    private String endWord;
    private int shortest;
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
       if (!wordList.contains(endWord)) {
           return res;
       }
       if (!wordList.contains(beginWord)) {
           wordList.add(beginWord);
       }
       this.wordList = wordList;
       this.beginWord = beginWord;
       this.endWord = endWord;
       visitedBFS = new int[wordList.size()];
       Arrays.fill(visitedBFS, -1);
       visitedDFS = new boolean[wordList.size()];
       int endIndex = 0;
       for (; endIndex < wordList.size(); endIndex ++) {
           if (wordList.get(endIndex).equals(endWord)) {
               break;
           }
       }
       G = new HashSet[wordList.size()];
       constructGraph();
       bfs(endIndex);
       List<String> path = new ArrayList<>();
       path.add(wordList.get(endIndex));
       dfs(endIndex, path, 1);
       return res;
    }

    // 建图
    private void constructGraph() {
        for (int i = 0; i < G.length; i ++) {
            G[i] = new HashSet<>();
        }
        for (int i = 0; i < wordList.size(); i ++) {
            for (int j = i + 1; j < wordList.size(); j ++) {
                if (isConnected(i, j)) {
                    G[i].add(j);
                    G[j].add(i);
                }
            }
        }
    }

    // 判断是否相邻
    private boolean isConnected(int i, int j) {
        String s1 = wordList.get(i);
        String s2 = wordList.get(j);
        int count = 0;
        for (int k = 0; k < s1.length(); k ++) {
            if (s1.charAt(k) != s2.charAt(k)) {
                count ++;
            }
            if (count > 1) {
                return false;
            }
        }
        return true;
    }

    // 查找最短路径长度
    private void bfs(int endIndex) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(endIndex);
        visitedBFS[endIndex] = 1;
        while (!queue.isEmpty()) {
            int cur = queue.remove();
            for (int next : G[cur]) {
                if (visitedBFS[next] == -1) {
                    visitedBFS[next] = visitedBFS[cur] + 1;
                    queue.add(next);
                    if (wordList.get(next).equals(beginWord)) {
                        shortest = visitedBFS[next];
                        return;
                    }
                }
            }
        }
    }

    private void dfs(int cur, List<String> path, int count) {
        if (count > shortest) {
            return;
        }
        if (count == shortest) {
            if (wordList.get(cur).equals(beginWord)) {
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int next : G[cur]) {
            if (!visitedDFS[next]) {
                visitedDFS[next] = true;
                path.addFirst(wordList.get(next));
                dfs(next, path, count + 1);
                path.removeFirst();
                visitedDFS[next] = false;
            }
        }
    }
}