题目描述
给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。
示例 1:
输入: s = "1^0|0|1", result = 0
输出: 2
解释: 两种可能的括号方法是
1^(0|(0|1))
1^((0|0)|1)
示例 2:
输入: s = "0&0&0&1^1|0", result = 1
输出: 10
提示：
解法
方法一：记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution:
def countEval(self, s: str, result: int) -> int:
@cache
def dfs(s):
res = [0] * 2
if s in '01':
res[int(s)] = 1
return res
for k, op in enumerate(s):
if op in '&^|':
left, right = dfs(s[:k]), dfs(s[k + 1 :])
for i, v1 in enumerate(left):
for j, v2 in enumerate(right):
if op == '&':
v = i & j
elif op == '^':
v = i ^ j
elif op == '|':
v = i | j
res[v] += v1 * v2
return res
ans = dfs(s)
return ans[result] if 0 <= result < 2 else 0
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | class Solution {
private Map<String, int[]> memo;
public int countEval(String s, int result) {
memo = new HashMap<>();
int[] ans = dfs(s);
return result == 0 || result == 1 ? ans[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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | class Solution {
public:
unordered_map<string, vector<int>> memo;
int countEval(string s, int result) {
vector<int> ans = dfs(s);
return result == 0 || result == 1 ? ans[result] : 0;
}
vector<int> dfs(string s) {
if (memo.count(s)) return memo[s];
vector<int> res(2);
if (s.size() == 1) {
res[s[0] - '0'] = 1;
return res;
}
for (int k = 0; k < s.size(); ++k) {
if (s[k] == '0' || s[k] == '1') continue;
vector<int> left = dfs(s.substr(0, k));
vector<int> right = dfs(s.substr(k + 1, s.size() - k));
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int v = 0;
if (s[k] == '&')
v = i & j;
else if (s[k] == '|')
v = i | j;
else if (s[k] == '^')
v = i ^ j;
res[v] += left[i] * right[j];
}
}
}
memo[s] = res;
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | 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
}
ans := dfs(s)
if result == 0 || result == 1 {
return ans[result]
}
return 0
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 | class Solution {
private var memo = [String: [Int]]()
func countEval(_ s: String, _ result: Int) -> Int {
memo = [:]
let ans = dfs(s)
return result == 0 || result == 1 ? ans[result] : 0
}
private func dfs(_ s: String) -> [Int] {
if let res = memo[s] {
return res
}
var res = [0, 0]
if s.count == 1 {
res[Int(String(s))!] = 1
return res
}
for k in 0..<s.count {
let index = s.index(s.startIndex, offsetBy: k)
let op = String(s[index])
if op == "&" || op == "|" || op == "^" {
let left = dfs(String(s[s.startIndex..<index]))
let right = dfs(String(s[s.index(after: index)...]))
for i in 0...1 {
for j in 0...1 {
var 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[s] = res
return res
}
}
|