面试题 08.14. 布尔运算 

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
49
50
51
52
53
54
class Solution {
    public int countEval(String s, int result) {
        // 定义 dp[i][j][k] 为区间 s[i, j] 组成布尔结果 result 的方案数
        int[][][] dp = new int[s.length()][s.length()][2];
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                dp[i][j] = new int[2];
                Arrays.fill(dp[i][j], -1);
            }
        }

        return getCount(dp, s, 0, s.length() - 1, result);
    }

    private int getCount(int[][][] dp, String s, int startIndex, int endIndex, int result) {
        if (startIndex == endIndex) {
            return s.charAt(startIndex) - '0' == result ? 1 : 0;
        }

        if (dp[startIndex][endIndex][result] != -1) {
            return dp[startIndex][endIndex][result];
        }

        int count = 0;

        // split to: [startIndex, k] and [k + 2, endIndex]
        for (int k = startIndex; k <= endIndex - 2; k += 2) { // 注意此处是 k += 2, 即 k 始终指向数字
            char operator = s.charAt(k + 1);
            for (int i = 0; i <= 1; i++) {
                for (int j = 0; j <= 1; j++) {
                    if (calc(operator, i, j) == result) {
                        count += getCount(dp, s, startIndex, k, i) * getCount(dp, s, k + 2, endIndex, j);
                    }
                }
            }
        }

        dp[startIndex][endIndex][result] = count;
        return count;
    }

    private int calc(char operator, int x, int y) {
        switch (operator) {
            case '&':
                return x & y;
            case '|':
                return x | y;
            case '^':
                return x ^ y;
            default:
                throw new IllegalArgumentException("Unsupported operator: " + operator);
        }
    }
}

References

面试题 08.14. 布尔运算