126. Word Ladder II

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return Collections.emptyList();
        }

        Map<String, Integer> wordToEdgeCountMap = new HashMap<>();
        wordToEdgeCountMap.put(beginWord, 0);
        Map<String, List<String>> wordToFromWordList = new HashMap<>();

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);

        int edgeCount = 1;
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                String word = queue.poll();
                for (int j = 0; j < word.length(); j++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        String nextWord = word.substring(0, j) + c + word.substring(j + 1);
                        if (nextWord.equals(word)) {
                            continue;
                        }

                        if (wordSet.contains(nextWord)) {
                            // 注意此处无论是否访问 nextWord 都需要添加至 wordToFromWordList, 否则 fromWordList 里面只会存在一个节点
                            wordToFromWordList.computeIfAbsent(nextWord, k -> new ArrayList<>()).add(word);

                            if (wordToEdgeCountMap.containsKey(nextWord)) {
                                continue;
                            }

                            wordToEdgeCountMap.put(nextWord, edgeCount);
                            queue.offer(nextWord);
                        }
                    }
                }
            }

            edgeCount++;
        }

        List<List<String>> resultList = new ArrayList<>();
        Deque<String> sequence = new LinkedList<>();
        dfs(resultList, sequence, endWord, beginWord, wordToEdgeCountMap, wordToFromWordList);
        return resultList;
    }

    private void dfs(List<List<String>> resultList, Deque<String> sequence, String word, String beginWord, Map<String, Integer> wordToEdgeCountMap, Map<String, List<String>> wordToFromWordList) {
        if (word.equals(beginWord)) {
            sequence.addFirst(word);
            resultList.add(new ArrayList<>(sequence));
            sequence.removeFirst(); // 注意移除
            return;
        }

        List<String> fromWordList = wordToFromWordList.get(word);
        // 注意判空，可能存在单词无法通过其他单词转换得到
        if (fromWordList != null) {
            for (String fromWord : fromWordList) {
                if (wordToEdgeCountMap.get(fromWord) + 1 == wordToEdgeCountMap.get(word)) {
                    sequence.addFirst(word);
                    dfs(resultList, sequence, fromWord, beginWord, wordToEdgeCountMap, wordToFromWordList);
                    sequence.removeFirst();
                }
            }
        }
    }
}

Reference

126. Word Ladder II