126. 单词接龙 II

126. 单词接龙 II

---

需要注意的是，由于要找最短路径，连接 dot 与 lot 之间的边就不可以被记录下来，同理连接 dog 与 log 之间的边也不可以被记录。这是因为经过它们的边一定不会是最短路径。因此在广度优先遍历的时候，需要记录的图的关系如下图所示。

在广度优先遍历的时候，我们需要记录：从当前的单词 currWord 只变化了一个字符以后，且又在单词字典中的单词 nextWord 之间的单向关系（虽然实际上无向图，但是广度优先遍历是有方向的，我们解决这个问题可以只看成有向图），记为 from，它是一个映射关系：键是单词，值是广度优先遍历的时候从哪些单词可以遍历到「键」所表示的单词，使用哈希表来保存。

---

Java代码：牛逼格拉斯！

class Solution {public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {List<List<String>> res = new ArrayList<>();Set<String> dict = new HashSet<>(wordList);if (!dict.contains(endWord)) {return res;}Map<String, Integer> steps = new HashMap<>();  Map<String, Set<String>> from = new HashMap<>();   // 无向图，记录层数boolean found = bfs(beginWord, endWord, dict, steps, from);  // 构建无向图if (found) {Deque<String> path = new ArrayDeque<>();  // 从尾往前addpath.add(endWord);dfs(from, path, beginWord, endWord, res);  // 开始回溯}return res;}private void dfs(Map<String, Set<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);dfs(from, path, beginWord, precursor, res);  // from有向图path.removeFirst();}}private boolean bfs(String beginWord, String endWord, Set<String> dict, Map<String, Integer> steps, Map<String, Set<String>> from) {int wordLen = beginWord.length();int step = 0;steps.put(beginWord, step);  boolean found = false;dict.remove(beginWord);Queue<String> queue = new LinkedList<>();queue.offer(beginWord);  // 用于BFS层搜索while (!queue.isEmpty()) {step++;int size = queue.size();for (int i = 0; i < size; i++) {  // 遍历队列：这一层的String currWord = queue.poll();char[] charArray = currWord.toCharArray();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) && steps.get(nextWord) == step) { // 归一的时候出现，即dog log到cog的时候from.get(nextWord).add(currWord);  // from: 广度优先遍历的时候从哪些单词可以遍历到「键」所表示的单词}                                      // 遍历第i层的时候，step == i + 1; if (!dict.contains(nextWord)) {  // 在当前层遍历的时候，已去除自身，下一层入队列，并去除在dict的记录continue;}// System.out.println(nextWord);dict.remove(nextWord);queue.offer(nextWord); // 进入到此处的都是下一层的，下一层入队列，并记录层数。当前层的已经被过滤掉了steps.put(nextWord, step);  // 记录nextWord的层数from.putIfAbsent(nextWord, new HashSet<>());  // from是映射图from.get(nextWord).add(currWord);  // currWord映射到nextWord，有向图if (nextWord.equals(endWord)) { // 不能在这里进行break，要继续填充endWord的setfound = true;}}charArray[j] = origin;}}if (found) {  // 每一层结束后判断，找到最短路径，退出whilebreak;}}return found;}
}