题目:
给定一个布尔表达式和一个期望的布尔结果 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
分析:
按运算符划分为子问题,例如s = "1^0|0|1" 可以分为:
1 ^ 0|0|1
1^0 | 0|1
1^0|0 | 1
三个子问题,同时对子问题递归求解。还要将已经算出的子问题的结果存储起来,可以使用map 也可以利用数组。当前解由左右两部分和中间的运算符计算得出。
程序:
class Solution { public int countEval(String s, int result) { if(s.length() == 1){ if(s.equals(String.valueOf(result))) return 1; else return 0; } int len = s.length(); int res = 0; for(int i = 0; i < len; ++i){ if(s.charAt(i) == '1' || s.charAt(i) == '0') continue; String left = s.substring(0, i); String right = s.substring(i + 1); if(map.get(left+"0") == null) map.put(left+"0", countEval(left, 0)); if(map.get(left+"1") == null) map.put(left+"1", countEval(left, 1)); if(map.get(right+"0") == null) map.put(right+"0", countEval(right, 0)); if(map.get(right+"1") == null) map.put(right+"1", countEval(right, 1)); int left_0 = map.get(left+"0"); int left_1 = map.get(left+"1"); int right_0 = map.get(right+"0"); int right_1 = map.get(right+"1"); if(s.charAt(i) == '&'){ if(result == 0){ res += (left_0 * right_0 + left_0 * right_1 + left_1 * right_0); }else{ res += (left_1 * right_1); } }else if(s.charAt(i) == '|'){ if(result == 0){ res += (left_0 * right_0); }else{ res += (left_1 * right_1 + left_0 * right_1 + left_1 * right_0); } }else{ if(result == 0){ res += (left_1 * right_1 + left_0 * right_0); }else{ res += (left_0 * right_1 + left_1 * right_0); } } } return res; } private HashMap<String, Integer> map = new HashMap<>(); }
class Solution { public int countEval(String s, int result) { dp = new int[s.length()][s.length()][]; helper(s, 0, s.length()-1, result); return dp[0][s.length()-1][result]; } private void helper(String s, int l, int r, int result){ if(dp[l][r] != null) return; if(l == r){ if(s.charAt(l) == '1'){ dp[l][r] = new int[]{0, 1}; return; }else{ dp[l][r] = new int[]{1, 0}; return; } } dp[l][r] = new int[]{0, 0}; for(int i = l; i < r; ++i){ if(s.charAt(i) == '1' || s.charAt(i) == '0') continue; helper(s, 0, i-1, result); helper(s, i+1, r, result); if(s.charAt(i) == '&'){ dp[l][r][0] += dp[l][i-1][0] * dp[i+1][r][1] + dp[l][i-1][1] * dp[i+1][r][0] + dp[l][i-1][0] * dp[i+1][r][0]; dp[l][r][1] += dp[l][i-1][1] * dp[i+1][r][1]; }else if(s.charAt(i) == '|'){ dp[l][r][0] += dp[l][i-1][0] * dp[i+1][r][0]; dp[l][r][1] += dp[l][i-1][0] * dp[i+1][r][1] + dp[l][i-1][1] * dp[i+1][r][0] + dp[l][i-1][1] * dp[i+1][r][1]; }else{ dp[l][r][0] += dp[l][i-1][0] * dp[i+1][r][0] + dp[l][i-1][1] * dp[i+1][r][1]; dp[l][r][1] += dp[l][i-1][0] * dp[i+1][r][1] + dp[l][i-1][1] * dp[i+1][r][0]; } } } private int[][][] dp; }