README.md

面试题 08.14. 布尔运算

English Version

题目描述

给定一个布尔表达式和一个期望的布尔结果 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

提示：

• 运算符的数量不超过 19 个

解法

方法一：记忆化搜索

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

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

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

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
}