題目：

題解：

class Solution {public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {List<List<String>> res = new ArrayList<>();// 因為需要快速判斷擴展出的單詞是否在 wordList 里，因此需要將 wordList 存入哈希表，這里命名為「字典」Set<String> dict = new HashSet<>(wordList);// 特殊用例判斷if (!dict.contains(endWord)) {return res;}dict.remove(beginWord);// 第 1 步：廣度優先搜索建圖// 記錄擴展出的單詞是在第幾次擴展的時候得到的，key：單詞，value：在廣度優先搜索的第幾層Map<String, Integer> steps = new HashMap<String, Integer>();steps.put(beginWord, 0);// 記錄了單詞是從哪些單詞擴展而來，key：單詞，value：單詞列表，這些單詞可以變換到 key ，它們是一對多關系Map<String, List<String>> from = new HashMap<String, List<String>>();int step = 1;boolean found = false;int wordLen = beginWord.length();Queue<String> queue = new ArrayDeque<String>();queue.offer(beginWord);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {String currWord = queue.poll();char[] charArray = currWord.toCharArray();// 將每一位替換成 26 個小寫英文字母for (int j = 0; j < wordLen; j++) {char origin = charArray[j];for (char c = 'a'; c <= 'z'; c++) {charArray[j] = c;String nextWord = String.valueOf(charArray);if (steps.containsKey(nextWord) && step == steps.get(nextWord)) {from.get(nextWord).add(currWord);}if (!dict.contains(nextWord)) {continue;}// 如果從一個單詞擴展出來的單詞以前遍歷過，距離一定更遠，為了避免搜索到已經遍歷到，且距離更遠的單詞，需要將它從 dict 中刪除dict.remove(nextWord);// 這一層擴展出的單詞進入隊列queue.offer(nextWord);// 記錄 nextWord 從 currWord 而來from.putIfAbsent(nextWord, new ArrayList<>());from.get(nextWord).add(currWord);// 記錄 nextWord 的 stepsteps.put(nextWord, step);if (nextWord.equals(endWord)) {found = true;}}charArray[j] = origin;}}step++;if (found) {break;}}// 第 2 步：回溯找到所有解，從 endWord 恢復到 beginWord ，所以每次嘗試操作 path 列表的頭部if (found) {Deque<String> path = new ArrayDeque<>();path.add(endWord);backtrack(from, path, beginWord, endWord, res);}return res;}public void backtrack(Map<String, List<String>> from, Deque<String> path, String beginWord, String cur, List<List<String>> res) {if (cur.equals(beginWord)) {res.add(new ArrayList<>(path));return;}for (String precursor : from.get(cur)) {path.addFirst(precursor);backtrack(from, path, beginWord, precursor, res);path.removeFirst();}}
}