☆☆☆☆☆思路：本题是127题的进阶版，需要将找到的最短路径存储下来。
方法1：BFS。在到达最短路径所在的层时，记录并输出所有符合条件的路径。
1. 127题的队列只存储每一层的元素，本题中队列需要存储每层添加元素之后的结果。
2. 如果该层添加的某一个单词符合目标单词，则该路径为最短路径，该层为最短路径所在的层，但此时不能直接返回结果，必须将该层遍历完，将该层所有符合的结果都添加进结果集；
3.每层添加单词的时候，不能直接添加到总的已访问单词集合中，需要每层有一个单独的该层访问的单词集，该层结束之后，再会合到总的已访问单词集合中，原因就是因为2
举例：该层遇到目标单词，有两条路径都可以遇到，但是先到达的将该单词添加进 visited 中，会导致第二条路径无法添加。
方法2：双向BFS + DFS
代码1：BFS（耗时390ms）
class Solution { public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) { Set<String> dictSet = new HashSet<>(wordList); List<List<String>> res = new ArrayList<>(); if (dictSet.size() == 0 || !dictSet.contains(endWord)) { return res; } // 累积每一层的结果队列 Queue<List<String>> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); List<String> list = new ArrayList<>(Arrays.asList(beginWord)); queue.offer(list); visited.add(beginWord); // 是否到达符合条件的层：如果该层添加的某一单词符合目标单词，则说明截止该层的所有解为最短路径，停止循环 boolean isFound = false; while (!queue.isEmpty() && !isFound) { // 上一层的结果队列 int size = queue.size(); // 该层添加的所有元素：每层必须在所有结果都添加完新的单词之后，再将这些单词统一添加到已使用单词集合 // 如果直接添加到 visited 中，会导致该层本次结果添加之后的相同添加行为失败 Set<String> subVisited = new HashSet<>(); for (int i = 0; i < size; i++) { List<String> path = queue.poll(); // 获取该路径上一层的单词 String cur = path.get(path.size() - 1); char[] chars = cur.toCharArray(); for (int j = 0; j < cur.length(); j++) { char temp = chars[j]; for (char k = 'a'; k <= 'z'; k++) { if (k == temp) continue; chars[j] = k; String newWord = String.valueOf(chars); // 符合条件：在 wordList 中 && 之前的层没有使用过 if (dictSet.contains(newWord) && !visited.contains(newWord)) { // 生成新的路径 List<String> pathList = new ArrayList<>(path); pathList.add(newWord); if (newWord.equals(endWord)) { isFound = true; res.add(pathList); } // 将该路径添加到该层队列中 queue.offer(pathList); // 将该单词添加到该层已访问的单词集合中 subVisited.add(newWord); } } chars[j] = temp; } } // 将该层所有访问的单词添加到总的已访问集合中 visited.addAll(subVisited); } return res; } }
代码2：双向BFS + DFS
M
参考：