Leetcode No.126 单词接龙 II（BFS）

示例 1：
 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
 解释：存在 2 种最短的转换序列：
 "hit" -> "hot" -> "dot" -> "dog" -> "cog"
 "hit" -> "hot" -> "lot" -> "log" -> "cog"
示例 2：
 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
 输出：[]
 解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
提示：
 1 <= beginWord.length <= 7
 endWord.length == beginWord.length
 1 <= wordList.length <= 5000
 wordList[i].length == beginWord.length
 beginWord、endWord 和 wordList[i] 由小写英文字母组成
 beginWord != endWord
 wordList 中的所有单词 互不相同

public 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<>();
        steps.put(beginWord, 0);
        //记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系
        Map<String, List<String>> from = new HashMap<>();
        //层数
        int step = 1;
        boolean found = false;
        int wordLen = beginWord.length();
        Queue<String> queue = new LinkedList<>();
        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);
                        //currWord可以拓展到nextWord且nextWord在第step层
                        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 而来,putIfAbsent如果传入key对应的value已经存在，就返回存在的value，不进行替换
                        from.putIfAbsent(nextWord, new ArrayList<>());
                        from.get(nextWord).add(currWord);
                        //记录 nextWord 的 step
                        steps.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);
            dfs(from, path, beginWord, endWord, res);
        }
        return res;
    }

    public void dfs(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);
            dfs(from, path, beginWord, precursor, res);
            path.removeFirst();
        }
    }

    public static void main(String[] args) {
        String beginWord = "hit";
        String endWord = "cog";
        String[] wordList = {"hot","dot","dog","lot","log","cog"};
        List<String> wordList2=new ArrayList<String>(Arrays.asList(wordList));
        Solution solution=new Solution();
        List<List<String>> rs=solution.findLadders(beginWord,endWord,wordList2);
        for(List<String> list:rs){
            for(String s:list){
                System.out.print(s+"->");
            }
            System.out.println();
        }
    }
}