BFS找到最短路, 在这个过程中建图
DFS这张图, 对深度超过最短路的路径剪枝

复杂度不会算

class Solution {
    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();

    Map<String, Set<String>> graph = new HashMap<>();

    Map<String, Integer> dist = new HashMap<>();
    Set<String> set = new HashSet<>();

    int targetDist = 0;

    Set<String> setDfs = new HashSet<>();

    public void dfs(String cur, String target, int curLevel){
        if(curLevel > targetDist) return;
        if(cur.equals(target)){
            ans.add(new ArrayList(path));
            return;
        }
        for(String outer : graph.get(cur)){ 
            if(dist.get(outer) != curLevel + 1){
                continue;
            }
            setDfs.add(outer);
            path.add(outer);
            dfs(outer, target, curLevel + 1);
            path.remove(path.size() - 1);
        }
    }




    public List<List<String>> findLadders(String begin, String end, List<String> wordList) {
        for(String word : wordList) set.add(word);
        Queue<String> q = new LinkedList<>();
        q.offer(begin);
        int step = 0;
        dist.put(begin, 0);
        while(!q.isEmpty()){
            int sz = q.size();
            for(int k = 0; k < sz; k++){
                String word = q.poll();

                for(int i = 0; i < begin.length(); i++){
                    for(char c = 'a'; c <= 'z'; c++){
                        String newWord;
                        if (i == 0){
                            newWord = c+ word.substring(i + 1);
                        } else if(i == begin.length() - 1){
                            newWord = word.substring(0, i) + c;
                        } else {
                            newWord = word.substring(0, i) + c + word.substring(i + 1);
                        }    
                        if(newWord.equals(word)){
                            continue;
                        }
                        if(!set.contains(newWord)){
                            continue;
                        }                           
                        if(graph.getOrDefault(newWord, null) == null){
                            graph.put(newWord, new HashSet<>());
                        }
                        if(graph.getOrDefault(word, null) == null){
                            graph.put(word, new HashSet<>());
                        }
                        graph.get(newWord).add(word);
                        graph.get(word).add(newWord);

                        if(!dist.containsKey(newWord)){
                            dist.put(newWord, dist.get(word) + 1);
                            q.offer(newWord);
                        }

                    }
                }
            }
            step++;
        }
        if(!dist.containsKey(end)) return ans;

        targetDist = dist.get(end);
        path.add(begin);
        dfs(begin, end, 0);


        return ans;
    }

}