126. Word Ladder II

Problem:
Get all path from word ladder.

Analysis:
BFS + DFS. BFS is responsible for creating the graph. DFS is responsible for getting all the solutions.

Need to construct a tree that endWord is the root. Then use DFS to traverse the tree.

Solution:

visited set stores the words that visited at current level. One set is ok to get the shortest distance, with 2 sets, we are able to get all path.

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        if (wordList.size() == 0 || wordList == null)
            return res;
        Set<String> visited = new HashSet<>();
        Set<String> unvisited = new HashSet<>(wordList);
        Map<String, List<String>> map = new HashMap<>();
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int curNum = 1; // # of words at cur level
        int nextNum = 0; // # of words at next level
        boolean found = false;
        
        while(!queue.isEmpty()) {
            String curWord = queue.poll();
            curNum--;
            for (int i = 0; i < curWord.length(); i++) {
                char[] temp = curWord.toCharArray();
                for (char j = 'a'; j <= 'z'; j++) {
                    temp[i] = j;
                    String newWord = new String(temp);
                    if (unvisited.contains(newWord)) {
                        if (visited.add(newWord)) { // first time visit, add to queue
                            queue.offer(newWord);
                            nextNum++;
                        }
                        if (map.containsKey(newWord)) {
                            map.get(newWord).add(curWord);
                        } else {
                            List<String> list = new ArrayList<>();
                            list.add(curWord);
                            map.put(newWord, list);
                        }
                        if (newWord.equals(endWord)) {
                            found = true;
                        }
                    }
                }
            }
            
            if (curNum == 0) {
                if (found) break;
                curNum = nextNum; // go to next level
                nextNum = 0;
                unvisited.removeAll(visited);
                visited.clear();
            }
        }
        
        dfs(map, res, new ArrayList<>(), endWord, beginWord);
        
        return res;
    }
    
    private void dfs(Map<String, List<String>> map, List<List<String>> res, List<String> temp, String endWord, String beginWord) {
        if (endWord.equals(beginWord)){
            temp.add(0,beginWord);
            res.add(new ArrayList<>(temp));
            temp.remove(0);
            return;
        }
        
        temp.add(0, endWord);
        if (map.containsKey(endWord)) {
            for (String neib: map.get(endWord)) {
                dfs(map, res, temp, neib, beginWord);
            }
        }
       
        temp.remove(0);
    }
}