[LC] 126. Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        Map<String, List<String>> graph = new HashMap<>();
        Map<String, Integer> distance = new HashMap<>();
        Set<String> wordSet = new HashSet<>(wordList);
        wordSet.add(beginWord);
        if (!wordSet.contains(endWord)) {
            return res;
        }
        bfs(endWord, beginWord, graph, distance, wordSet);
        dfs(graph, distance, new ArrayList<String>(), res, beginWord, endWord);
        return res;
    }
    
    private void bfs(String start, String end, Map<String, List<String>> graph, Map<String, Integer> distance, Set<String> wordSet) {
        for (String word : wordSet) {
            graph.put(word, new ArrayList<>());
        }
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        distance.put(start, 0);
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            for (String nxt: getNext(cur, wordSet)) {
                // still need to construct graph even if visited
                graph.get(nxt).add(cur);
                if (distance.containsKey(nxt)) {
                    continue;
                }
                queue.offer(nxt);
                distance.put(nxt, distance.get(cur) + 1);
            }
        }
    }
    
    private List<String> getNext(String cur, Set<String> wordSet) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < cur.length(); i++) {
            for (char j = 'a'; j <= 'z'; j++) {
                String nxt = cur.substring(0, i) + j + cur.substring(i + 1);
                if (wordSet.contains(nxt)) {
                    list.add(nxt);
                }
            }            
        }
        return list;
    }
    
    private void dfs(Map<String, List<String>> graph, Map<String, Integer> distance, List<String> path, List<List<String>> res, String cur, String end) {
        path.add(cur);
        if (cur.equals(end)) {
            res.add(new ArrayList<>(path));
        } else {
            for (String nxt: graph.get(cur)) {
                if (distance.get(nxt) + 1 == distance.get(cur)) {
                    dfs(graph, distance, path, res, nxt, end);
                }
            }            
        }
        path.remove(path.size() - 1);
    }
}