双向广搜

---

基本介绍

常见用途 1：小优化

bfs 的剪枝策略，分两侧展开分支，哪侧数量少就从哪侧展开，直到相遇

常见用途 2：重要！本体！用于解决特征很明显的一类问题

（1）特征：全量样本不允许递归完全展开，但是半量样本可以完全展开

（2）过程：把数据分成两部分，每部分各自展开计算结果，然后设计两部分结果的整合逻辑

单词接龙

题目链接

https://leetcode.cn/problems/word-ladder/

思路分析

双向广搜用途 1 的模板题，从两侧开始搜索，一定程度上减少展开次数，提高搜索效率，遵循哪侧展开少从哪侧开始搜索的原则，检查两侧搜索结果是否一致，如果一致说明相遇，搜索结束

代码实现

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return 0;
        }
        // 数量小的一侧
        HashSet<String> smallLevel = new HashSet<>();
        // 数量大的一侧
        HashSet<String> bigLevel = new HashSet<>();
        // 由数量小的一侧所口展出的下一层列表
        HashSet<String> nextLevel = new HashSet<>();
        smallLevel.add(beginWord);
        bigLevel.add(endWord);
        for (int len = 2; !smallLevel.isEmpty(); len++) {
            for (String w : smallLevel) {
                // 从小侧扩展
                char[] word = w.toCharArray();
                for (int j = 0; j < word.length; j++) {
                    // 每个字符从 a - z 替换
                    char old = word[j];
                    for (char change = 'a'; change <= 'z'; change++) {
                        // 不能替换自己
                        if (change != old) {
                            word[j] = change;
                            String next = String.valueOf(word);
                            // 检查大的一侧，如果存在说明相遇，直接返回
                            if (bigLevel.contains(next)) {
                                return len;
                            }
                            // 检查是否有效
                            if (dict.contains(next)) {
                                dict.remove(next);
                                nextLevel.add(next);
                            }
                        }
                    }
                    word[j] = old;
                }
            }
            // 谁小，谁作为下一轮的 small 继续搜索
            if (nextLevel.size() <= bigLevel.size()) {
                HashSet<String> tmp = smallLevel;
                // nextLevel 更小，作为下一轮的 smallLevel
                smallLevel = nextLevel;
                nextLevel = tmp;
            } else {
                HashSet<String> tmp = smallLevel;
                // bigLevel 更小，作为下一轮的 smallLevel
                smallLevel = bigLevel;
                bigLevel = nextLevel;
                nextLevel = tmp;
            }
            nextLevel.clear();
        }
        return 0;
    }
}

世界冰球锦标赛

题目链接

https://www.luogu.com.cn/problem/P4799

思路分析

代码实现

最接近目标值的子序列和

题目链接

https://leetcode.cn/problems/closest-subsequence-sum/

思路分析

代码实现