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<>();  // 从尾往前add
            path.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的set
                            found = true;
                        }
                    }
                    charArray[j] = origin;
                }
            }
            if (found) {  // 每一层结束后判断，找到最短路径，退出while
                break;
            }
        }
        return found;
    }
}