[数据结构与算法]126. 单词接龙 II

126. 单词接龙 II

方法：广度优先遍历、深度优先遍历（回溯）

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;
        }
        //因为从beginWord开始扩展，因此dict里一定不可以有beginWord
        dict.remove(beginWord);

        //第1步：广度优先遍历构建图
        //为了避免记录不需要的边，我们需要记录扩展出的单词是在第几次扩展的时候得到的，key:单词，value:在广度优先遍历的第几层
        //steps 记录了已经访问过的word集合，同时记录了在第几层访问到
        Map<String, Integer> steps = new HashMap<>();
        steps.put(beginWord, 0);
        //记录了单词是从哪些单词扩展而来的，key:单词，value:单词列表，这些单词可以变换到key，它们是一对多关系，dfs的时候会用到
        Map<String, Set<String>> from = new HashMap<>();
        boolean found = bfs(beginWord, endWord, dict, steps, from);
        
        //第2步：深度优先遍历找到所有解，从endWord恢复到beginWord，所以每次尝试操作path列表的头部
        if (found) {
            Deque<String> path = new ArrayDeque<>();
            path.add(endWord);
            dfs(from, path, beginWord, endWord, res);
        }
        return res;
    }

    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;
        boolean found = false;
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        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++) {
                        //将每一位替换成26个小写英文字母
                        charArray[j] = c;
                        String nextWord = String.valueOf(charArray);
                        //注意：这几行代码的逻辑先后顺序
                        if (steps.containsKey(nextWord) && steps.get(nextWord) == step) {
                            from.get(nextWord).add(currWord);
                        }
                        
                        if (!dict.contains(nextWord)) {
                            continue;
                        }
                        dict.remove(nextWord);
                        
                        //dict 和 steps承担了已经访问的功能
                        queue.offer(nextWord);
                        
                        //维护from,steps,found的定义
                        from.putIfAbsent(nextWord, new HashSet<>());
                        from.get(nextWord).add(currWord);
                        steps.put(nextWord, step);
                        if (nextWord.equals(endWord)) {
                            //注意：由于有多条路径到达endWord,找到以后不能立即退出，只需要设置found = true即可
                            found = true;
                        }
                    }
                    charArray[j] = origin;
                }
            }
            if (found) {
                break;
            }
        }
        return found;
    }


    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);
            path.removeFirst();
        }
    }
}