解释都在代码中

(BFS+DFS) $O(26nL^2)$

BFS来建图，DFS来搜索满足的情况

class Solution {
    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();
    // dist[i]：表示是从beginWord变成 dist[i]的key代表的字符串的最小次数
    Map<String, Integer> dist = new HashMap<>();
    // 存储的字典
    Set<String> S = new HashSet<>();
    Queue<String> q = new LinkedList<>();
    String beginWord;

    // BFS + DFS
    public List<List<String>> findLadders(String _beginWord, String endWord, List<String> wordList) {
        beginWord = _beginWord;
        S.addAll(wordList);

        dist.put(_beginWord, 0);
        q.add(_beginWord);
        // 枚举每个单词，然后枚举该单词的每一位字母，再枚举这一位的所有备选字母，然后再判断改变后的字符串是否存在。O(26nL^2)
        // 权值为1的最短路问题。
        // 宽搜来搜索从beginWord编导endWord的最小次数
        while(!q.isEmpty()) {
            String t = q.poll();
            for(int i = 0; i < t.length(); i ++) {
                char[] ch = t.toCharArray();
                // 变换
                for(char j = 'a'; j <= 'z'; j ++) {
                    if(ch[i] != j) {
                        ch[i] = j;
                        String t1 = new String(ch);
                        // 第一次搜索到该字符串
                        if(S.contains(t1) && !dist.containsKey(t1)) {
                            // 距离 + 1
                            dist.put(t1, dist.get(t) + 1);

                            // 加快执行。因为当前字符串t的第i个位置的变换情况已经结束，
                            // 当前的变换成其他字符已经不可能满足小于这个dist[t1]
                            if (t1.equals(endWord)) break;
                            q.add(t1);
                        }
                    }
                }
            }
        }
        // 如果不包含endWord，说明不能转换成功
        if (!dist.containsKey(endWord)) return ans;
        path.add(endWord);
        // 从endWord开始寻找，因为：减少不必要的dfs
        dfs(endWord);
        return ans;
    }
    // 这里只枚举了某个字符串到endWord的变换次数为1的
    public void dfs(String t) {
        if (t.equals(beginWord)) {
            List<String> temp = new ArrayList<>(path);
            Collections.reverse(temp);
            ans.add(temp);
        }else {
            for(int i = 0; i < t.length(); i ++) {
                char[] ch = t.toCharArray();
                for(char j = 'a'; j  <= 'z'; j ++) {
                    if(ch[i] != j) {
                        ch[i] = j;
                        String t1 = new String(ch);
                        // 剪枝。利用dist[i] + 1 == dist[t]的性质，才进行dfs
                        if(dist.containsKey(t1) && dist.get(t1) + 1 == dist.get(t)) {
                            path.add(t1);
                            dfs(t1);
                            // 回溯时，恢复现场
                            path.remove(path.size() - 1);
                        }
                    }
                }
            }
        }

    }
}