126. Word Ladder II

class Solution {

    List<List<String>> re = new ArrayList<>();

    Map<String, Integer> distance = new HashMap<>();
    Map<String, List<String>> map = new HashMap<>();

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        distance.put(beginWord, 0);
        for(String str : wordList) map.put(str, new ArrayList<>());
        if(!bfs(beginWord, endWord, new HashSet<>(wordList))) return re;
        List<String> list = new ArrayList<>();
        dfs(list, endWord, beginWord);
        return re;
    }

    void dfs(List<String> path, String crt, String start)
    {
        path.add(crt);
        System.out.println(path);
        if (crt.equals(start))
        {
            Collections.reverse(path);
            re.add(new ArrayList<String>(path));
            Collections.reverse(path);
        }
        else
        {
            for (String next : map.get(crt))
            {
                if (distance.containsKey(next) && distance.get(crt) == distance.get(next) + 1)
                {
                    dfs(path, next, start);
                }
            }
        }
        path.remove(path.size() - 1);
    }

    boolean bfs(String a, String b, Set<String> set)
    {
        boolean found = false;
        Queue<String> q = new LinkedList<>();
        q.offer(a);

        while(!q.isEmpty())
        {
            String cur = q.poll();
            if(cur.equals(b))
            {
                found = true;
            }
            for(String next : expand(cur, set))
            {
                map.get(next).add(cur);
                if(!distance.containsKey(next))
                {
                    distance.put(next, distance.getOrDefault(cur, 0) + 1);
                    q.offer(next);
                }

            }
        }
        return found;
    }

    List<String> expand(String crt, Set<String> dict)
    {

        List<String> expansion = new ArrayList<String>();

        for (int i = 0; i < crt.length(); i++)
        {
            for (char ch = 'a'; ch <= 'z'; ch++)
            {
                if (ch != crt.charAt(i))
                {
                    String expanded = crt.substring(0, i) + ch + crt.substring(i + 1);
                    if (dict.contains(expanded))
                    {
                        expansion.add(expanded);
                    }
                }
            }
        }

        return expansion;
    }



}