Skip to content

08.14. Boolean Evaluation

Description

Given a boolean expression consisting of the symbols 0 (false), 1 (true), & (AND), | (OR), and ^ (XOR), and a desired boolean result value result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result.

Example 1:


Input: s = "1^0|0|1", result = 0



Output: 2

Explanation: Two possible parenthesizing ways are:

1^(0|(0|1))

1^((0|0)|1)

Example 2:


Input: s = "0&0&0&1^1|0", result = 1



Output: 10

Note:

  • There are no more than 19 operators in s.

Solutions

Solution 1

 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
    }
}

Comments