127. 单词接龙

LeetCode： 127. 单词接龙

最短问题 >> bfs | 广度优先遍历

1. 广度优先遍历 >> 队列 Queue （先进先出）是 bfs 的核心
   1.1 visSet 存储已经走过的节点路径 （ 将 list 换成 set 可以更高效率的找到是否存在重复元素 ）

2. 双向广度优先遍历 >> 去掉了 Queue 队列 >> 使用了 两个 Set 来替代 bfs 核心
   2.1 Queue 队列的功能 可以通过 两个 Set 来模拟 >> beginWord 、endWord 同时向中间遍历
   2.2 每次遍历遍历范围集小的那个 Set
   2.3 其他与 广度优先遍历类似 >> 双向广度优先遍历的有点是 >> 搜索的范围集比原来的单边bfs更小 >> 效率稍快

广度优先遍历

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 提升查是否存在的效率 set -> O(1)
        Set<String> wordSet = new HashSet<>(wordList);

        // 从字典中移除本身
        wordSet.remove(beginWord);
        // bfs >>  队列的核心
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);

        // 记录是否访问过
        Set<String> visSet = new HashSet<>();
		// visSet.add(beginWord);
		
        int step = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                char[] charArray = queue.poll().toCharArray();
                for (int j = 0; j < charArray.length; j++) {
                    // 临时保存
                    char tempc = charArray[j];
                    for (int k = 0; k < 26; k++) {
                        charArray[j] = (char) ('a' + k);
                        String s = new String(charArray);
                        if(wordSet.contains(s)){
                            if(endWord.equals(s)){
                                return step + 1;
                            }
                            if(!visSet.contains(s)){
                                queue.offer(s);
                                // 加入访问
                                visSet.add(s);
                            }
                        }
                    }
                    charArray[j] = tempc;
                }
            }
            
           // 步长+1
           step++;
        }

        return 0;
    }

双向广度优先遍历

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);

        Set<String> visSet = new HashSet<>();

        // 模拟队列Queue
        // 在遍历的使用交替使用
        Set<String> beginSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();
        visSet.add(beginWord);
        visSet.add(endWord);
        beginSet.add(beginWord);
        endSet.add(endWord);


        int step = 1;
        while (!beginSet.isEmpty() && !endSet.isEmpty()){

            // 找出较小的那个 set
            if(beginSet.size() < endSet.size()){
                Set<String> temp = endSet;
                endSet = beginSet;
                beginSet = temp;
            }

            // 用来指向新的 beginSet
            Set<String> newNextSet = new HashSet<>();
            // 遍历较小的set
            for (String val : beginSet) {
                // 获得词
                char[] charArray = val.toCharArray();
                for (int i = 0; i < charArray.length; i++) {
                    char tempc = charArray[i];
                    for (int j = 0; j < 26; j++) {
                        charArray[i] = (char) ('a' + j);
                        String s = new String(charArray);

                        // 字典中有这个单词
                        if(wordSet.contains(s)){
                            // 这里稍微和单向广度遍历的不一样
                            if(endSet.contains(s)){
                                // 表示beginSet 和 endSet 之间的隧道打通了
                                return step + 1;
                            }

                            if(!visSet.contains(s)){
                                newNextSet.add(s);
                                // 添加进去
                                visSet.add(s);
                            }
                        }
                    }
                    charArray[i] = tempc;
                }
            }
            beginSet = newNextSet;
            step++;
        }

        return 0;
    }