LeetCode 面试题 08.14. 布尔运算
题目描述
题意分析
不改变数字和运算符的先后顺序，只通过括号改变布尔表达式的结合方式，统计结果等于
result的方案数。不同分组即使算出相同布尔值，也要分别计数；运算符只有&、|、^，操作数只有 0、1。
解法：枚举最后运算符并记忆子表达式计数
核心思路
[!blue]
任意完整的括号分组，都有一个最后执行的运算符。它把原表达式分成连续的左、右两部分；左右分别完成运算后，再由这个运算符合并。因此可以枚举每个运算符作为最后一步，把问题递归拆成两个更短的表达式。
dfs(s)同时返回两个计数：res[0]是子表达式结果为 0 的方案数，res[1]是结果为 1 的方案数。父运算可能用到左右任一种结果，不能只计算最终希望得到的那一种。子表达式只有一个数字时，得到该数字的方案恰好为 1，另一结果为 0。固定最后运算符后，枚举左右结果
i、j的四种组合。左边有left[i]种分组，右边有right[j]种，它们可以独立搭配，所以共有left[i] * right[j]种组合。按当前运算符算出v，把这个乘积加入res[v]；代码直接对 0、1 使用按位与、或、异或，结果就是对应的布尔值。不同最后运算符的位置对应不同的最外层划分，因此各位置的贡献相加；每个完整方案又只有唯一的最后运算符和左右分组，所以不会重复计算同一方案。递归一直缩短表达式，最终到达单个数字，覆盖了全部分组方式。
不同划分会反复求解相同子表达式，用字符串内容作为键缓存这两个计数即可。相同内容在不同位置的计算规则相同，可以复用结果；这是复用计算，不是把不同位置的方案合并掉，它们仍在各自的父划分中参与乘法计数。
解题步骤
- 创建本次调用的记忆表，从完整表达式开始递归。
- 若子表达式已经缓存，直接返回两个计数；若只剩一个数字，返回该数字对应计数为 1 的数组。
- 枚举合法运算符位置，将左右子串分别递归求值。
- 枚举左右结果 0、1，计算当前运算结果，并累加两边方案数的乘积。
- 将当前子表达式的两个总计数缓存，最后取出
result对应的次数。
代码实现
// 每个子表达式同时返回求值为 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)$。子表达式最多有 $O(n^2)$ 个，每个枚举 $O(n)$ 个分割，四种真假组合是常数开销。当前实现还会构造子串并计算字符串哈希，单次可能花费 $O(n)$，因此包含字符串操作的时间上界为 $O(n^4)$。
- 空间复杂度：Java 缓存的子串会保存各自字符内容，至多 $O(n^2)$ 个键、每个长 $O(n)$，空间上界为 $O(n^3)$；Go 子串共享原字符串底层内容，缓存键和计数占 $O(n^2)$。两者递归深度均为 $O(n)$。
关键点总结
[!green]
- 按最后执行的运算符划分，左右分组独立，贡献相乘；不同划分的贡献相加。
- 一个子表达式同时返回假、真两种计数，父层才能枚举完整真值组合。
- 题面最多 19 个运算符，全部括号分组数不超过第 19 个卡特兰数 1767263190，当前整数计数可以容纳。
易错点总结
[!yellow]
- 只能在运算符位置分割，不能把数字位置当成最后一步。
- 不能固定按原运算优先级求值，题目允许括号改变结合顺序，需要枚举所有根划分。
- 左右方案数应相乘，单独相加不能表示两边的全部搭配。
- 布尔结果相同不代表括号方案相同，不能用结果集合去重。
- 字符串键会产生构造或哈希开销，不能把下标区间缓存的复杂度直接套到当前代码上。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 241. 为运算表达式设计优先级 | 中等 | 同样枚举最后运算符，原题输出所有算术结果，本题把结果压缩为0和1的方案计数。 |
| 312. 戳气球 | 困难 | 同样通过选择最后一步拆成独立左右区间，原题取最优值，本题累计所有方案。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！