今天的題目為126.Word Ladder II，從單字beginWord到endWord的轉換序列，是一串單字 [beginWord -> s1 -> s2 -> ... -> sk]，需滿足以下條件：每一對相鄰單字只相差一個字母，每個 si（1 ≤ i ≤ k）都必須在字典 wordList 中，beginWord 不需要在 wordList 中，最後一個單字 sk 必須是endWord，回傳所有最短的轉換序列，如果不存在，則回傳空列表。每個序列應該是 [beginWord, s1, s2, ..., endWord]。

以下為程式碼：

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

        Map<String, List<String>> graph = new HashMap<>();
        Map<String, Integer> distance = new HashMap<>();
        bfs(beginWord, endWord, wordSet, graph, distance);
        List<String> path = new ArrayList<>();
        dfs(beginWord, endWord, graph, distance, path, results);
        return results;
    }

    private void bfs(String beginWord, String endWord, Set<String> wordSet,
                     Map<String, List<String>> graph, Map<String, Integer> distance) {
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        distance.put(beginWord, 0);

        while (!queue.isEmpty()) {
            String word = queue.poll();
            for (String neighbor : getNeighbors(word, wordSet)) {
                graph.computeIfAbsent(word, k -> new ArrayList<>()).add(neighbor);
                if (!distance.containsKey(neighbor)) {
                    distance.put(neighbor, distance.get(word) + 1);
                    queue.offer(neighbor);
                }
            }
        }
    }

    private void dfs(String current, String endWord, Map<String, List<String>> graph,
                     Map<String, Integer> distance, List<String> path, List<List<String>> results) {
        path.add(current);
        if (current.equals(endWord)) {
            results.add(new ArrayList<>(path));
        } else {
            for (String neighbor : graph.getOrDefault(current, new ArrayList<>())) {
                if (distance.get(neighbor) == distance.get(current) + 1) {
                    dfs(neighbor, endWord, graph, distance, path, results);
                }
            }
        }
        path.remove(path.size() - 1);
    }

    private List<String> getNeighbors(String word, Set<String> wordSet) {
        List<String> neighbors = new ArrayList<>();
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char old = chars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == old) continue;
                chars[i] = c;
                String newWord = new String(chars);
                if (wordSet.contains(newWord)) {
                    neighbors.add(newWord);
                }
            }
            chars[i] = old;
        }
        return neighbors;
    }
}

今天的真的好難。