Question

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

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
}