LeetCode 面试题 08.14. 布尔运算
目录
题目描述
题意分析
表达式由布尔值
0/1与运算符&、|、^交替组成。可以在不改变字符顺序的前提下任意添加括号，求最终结果等于给定result的括号方案数。不同括号方式对应不同的二叉表达式树。若枚举所有括号结构再逐个计算，会产生卡特兰数级别的重复搜索；同一个连续子表达式会在许多上层方案中被反复求值。
只记录某段“能否为真”还不够，因为题目要计数，而且父运算符同时需要左右两段为 0 和为 1 的方案数。因此每个子表达式都要返回一对计数
[falseCount, trueCount]。
解法：按根运算符切分 + 记忆化搜索
核心思路
对任意子表达式，枚举哪一个运算符作为整棵子树最后执行的根运算。根左边和右边分别形成两个独立子问题；只要知道两边得到 0/1 的方案数，就能按运算符真值表组合。
设左侧计数为
left[i]、右侧为right[j]，其中i,j ∈ {0,1}。对四种取值组合，计算v = i op j，向res[v]增加left[i] * right[j]。乘法来自左右括号方案的笛卡尔积，加法来自不同根位置或不同真假组合互斥。记忆化键使用子表达式内容；相同连续片段再次出现时直接返回已计算的两个计数。更标准的面试优化是传左右下标并用二维表缓存，可避免构造 substring，同时把状态明确成原串区间。
解题步骤
dfs(s)返回长度为 2 的数组，分别记录子表达式得到 0 和 1 的方案数。- 长度为 1 时是叶子：字符为几，就把对应计数设为 1。
- 枚举每个运算符位置
k，递归求左右子串的计数。- 枚举左右结果
i、j的四种组合，用当前运算符求v，累计乘积left[i] * right[j]。- 把当前子串结果写入缓存；顶层根据
result返回对应计数。以
s = "1^0|0|1"、result = 0为例，共有 5 种括号结构。其中1^((0|0)|1)与1^(0|(0|1))的右侧都为 1，最终得到 0；另外三种得到 1，因此答案是 2。递归会在不同根切分中多次遇到0|1等子串，缓存可直接复用。
代码实现
// 每个子表达式同时返回求值为 0 与 1 的方案数。
class Solution {
private Map<String, int[]> memo;
public int countEval(String s, int result) {
memo = new HashMap<>();
int[] answer = dfs(s);
return result == 0 || result == 1 ? answer[result] : 0;
}
private int[] dfs(String s) {
if (memo.containsKey(s)) {
return memo.get(s);
}
int[] res = new int[2];
if (s.length() == 1) {
res[Integer.parseInt(s)] = 1;
return res;
}
for (int k = 0; k < s.length(); ++k) {
char op = s.charAt(k);
if (op == '&' || op == '|' || op == '^') {
int[] left = dfs(s.substring(0, k));
int[] right = dfs(s.substring(k + 1));
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int v = 0;
if (op == '&') {
v = i & j;
} else if (op == '|') {
v = i | j;
} else if (op == '^') {
v = i ^ j;
}
res[v] += left[i] * right[j];
}
}
}
}
memo.put(s, res);
return res;
}
}
// 每个子表达式同时返回求值为 0 与 1 的方案数。
func countEval(s string, result int) int {
memo := map[string][]int{}
var dfs func(string) []int
dfs = func(s string) []int {
if v, ok := memo[s]; ok {
return v
}
res := make([]int, 2)
if len(s) == 1 {
res[s[0]-'0'] = 1
return res
}
for k, c := range s {
if c == '0' || c == '1' {
continue
}
left, right := dfs(s[:k]), dfs(s[k+1:])
for i, v1 := range left {
for j, v2 := range right {
v := 0
if c == '&' {
v = i & j
} else if c == '|' {
v = i | j
} else if c == '^' {
v = i ^ j
}
res[v] += v1 * v2
}
}
}
memo[s] = res
return res
}
answer := dfs(s)
if result == 0 || result == 1 {
return answer[result]
}
return 0
}
复杂度分析
- 时间复杂度：若以操作数个数
n计，连续区间状态有 $O(n^2)$ 个，每个状态枚举 $O(n)$ 个根运算符，核心 DP 为 $O(n^3)$。当前按字符串做键还会产生 substring 构造与哈希开销；用左右下标可稳定保持 $O(n^3)$。- 空间复杂度：$O(n^2)$ 保存区间计数，递归栈最深 $O(n)$；当前字符串键还会保存子串内容，实际常数与字符存储更大。
关键点总结
- 括号化表达式计数的核心是枚举“最后执行哪个运算符”，也就是枚举表达式树的根，而不是枚举第一步先算哪里。
- 每个区间必须同时保存真假两种计数，否则父节点无法完整套用真值表。
- 面试表达要说清组合为何相乘、不同切分为何相加，这是计数 DP 正确性的关键。
- 常见追问是改成自底向上区间 DP：按操作数区间长度递增，转移公式完全相同，可消除递归与 substring。
易错点总结
- 只统计目标值，不统计另一种值：父运算符可能需要任意真假组合；例如异或为真需要一真一假，缺一侧计数无法转移。
- 组合时相加而不是相乘：左边 2 种、右边 3 种的某个取值组合应贡献 6 种括号方案，不是 5 种。
- 把数字位置也当成切分点：会产生空子串或把运算符留在错误一侧；只能在
&、|、^处切分。- 基本情况把另一个计数也设为 1：单个
0只有一种求假方案，求真方案必须是 0。- 没有记忆化：长度增长后同一子串被指数级重复计算，迅速超时。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 312. 戳气球 | 困难 | 区间 DP |
| 486. 预测赢家 | 中等 | 区间 DP |
| 877. 石子游戏 | 中等 | 区间 DP |
| 887. 鸡蛋掉落 | 困难 | 区间 DP |
| 1000. 合并石头的最低成本 | 困难 | 区间 DP |
| 1690. 石子游戏 VII | 中等 | 区间 DP |