126 word ladder II

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new ArrayDeque<>();
        List<List<String>> ans = new ArrayList<>();
        Set<String> dict = new HashSet<>(wordList);
        //for backtracking，这里要用set防止重复parent
        Map<String, Set<String>> map = new HashMap<>();
        Set<String> visited = new HashSet<>();
        queue.offer(beginWord);
        visited.add(beginWord);
        boolean found = false;
        while(!queue.isEmpty()) {
            if (found) break;
            int size = queue.size();
            //思想就是每一层用tmpVisited暂存一下visited，主要是因为这一层是允许重复的
            //即允许这一层的不同word生成相同的下一层word（因为要得到所有路径嘛），
            //但是不允许这一层word在之前层中出现过
            Set<String> tmpVisited = new HashSet<>();
            for (int aa = 0; aa < size; aa++) {
                String str = queue.poll();
                if (str.equals(endWord)) {
                    found = true;
                    continue;
                }
                char[] array = str.toCharArray();
                for (int i = 0; i < array.length; i++) {
                    char ch = array[i];
                    for (int j = 0; j < 26; j++) {
                        if (j == ch - 'a') continue;
                        array[i] = (char)('a' + j);
                        String newStr = new String(array);
                        if (!dict.contains(newStr) || visited.contains(newStr)) continue;
                        tmpVisited.add(newStr);
                        Set<String> parents = map.get(newStr);
                        if (parents == null) parents = new HashSet<>();
                        parents.add(str);
                        map.put(newStr, parents);
                        queue.offer(newStr);
                    }
                    array[i] = ch;
                }
            }
            visited.addAll(tmpVisited);
        }
        if (!found) return ans;
        dfs(ans, map, new ArrayList<>(), endWord, beginWord);
        return ans;
    }
    private void dfs(List<List<String>> ans, Map<String, Set<String>> map, List<String> res, 
                     String endWord, String beginWord) {
        if (endWord.equals(beginWord)) {
            res.add(endWord);
            List<String> revres = new ArrayList<>(res);
            // Collections里面有reverse api
            Collections.reverse(revres);
            ans.add(new ArrayList<>(revres));
            // 注意这里也是要remove的 返回上一层之前都要remove
            // 你要是不想的话就不要在原来的上面add，reverse之后再把beginword add上去
            res.remove(endWord);
            return;
        }
        Set<String> list = map.get(endWord);
        // 防止没有可行解时npe
        if (list == null) return;
        res.add(endWord);
        for (String str : list) {
            dfs(ans, map, res, str, beginWord);
        }
        res.remove(res.size() - 1);
    }
}

这题的时间要求太操蛋了，但是核心思想就是暂存visited来允许重复

如何获得所有路径：bfs自身善于获得最短路径长度，但是并不擅长记录走过的路径，需要记录当前string和能得到它的parents，然后通过dfs倒着从结果倒推出找出所有路径

同时注意如果要backtrack的话map应该记录什么