难度: Medium
给定一个布尔表达式和一个期望的布尔结果 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
提示：
运行时间: 34 ms
内存: 16.1 MB
class Solution:
def countEval(self, s: str, result: int) -> int:
n = len(s)
dp = [[[0] * 2 for _ in range(n)] for _ in range(n)]
for i in range(len(s)):
if s[i] in ['0', '1']:
dp[i][i][ord(s[i])-ord('0')] = 1
for l in range(2, len(s) + 1, 2):
for i in range(0, len(s) - l + 1, 2):
j = i + l
for k in range(i + 1, j, 2):
if s[k] == '&':
dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][1]
dp[i][j][0] += dp[i][k - 1][1] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1] + dp[i][k - 1][0] * dp[k + 1][j][0]
elif s[k] == '|':
dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1] + dp[i][k - 1][1] * dp[k + 1][j][1]
dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0]
elif s[k] == '^':
dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0] + dp[i][k - 1][1] * dp[k + 1][j][1]
dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1]
# print(dp)
return dp[0][n - 1][result]
此题解采用动态规划的方式来解决问题。定义dp[i][j][0]和dp[i][j][1]为布尔表达式从索引i到j计算结果为False和True的方法数。初始化时，如果字符是'0'或'1'，则相应的dp[i][i][0]或dp[i][i][1]设为1。对于表达式中的每个可能的子段，使用变量k遍历所有可能的操作符位置，根据操作符的类型（AND、OR、XOR），更新dp数组。例如，对于AND操作，当两边都为True时结果才为True；对于OR操作，任意一边为True结果即为True；对于XOR操作，两边不同结果才为True。这样从最小的子表达式逐步扩大范围，直至得出整个表达式的结果。
时间复杂度: O(n^3)
空间复杂度: O(n^2)
class Solution:
def countEval(self, s: str, result: int) -> int:
n = len(s)
dp = [[[0] * 2 for _ in range(n)] for _ in range(n)]
for i in range(len(s)):
if s[i] in ['0', '1']:
dp[i][i][ord(s[i])-ord('0')] = 1
for l in range(2, len(s) + 1, 2):
for i in range(0, len(s) - l + 1, 2):
j = i + l
for k in range(i + 1, j, 2):
if s[k] == '&':
dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][1]
dp[i][j][0] += dp[i][k - 1][1] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1] + dp[i][k - 1][0] * dp[k + 1][j][0]
elif s[k] == '|':
dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1] + dp[i][k - 1][1] * dp[k + 1][j][1]
dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0]
elif s[k] == '^':
dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0] + dp[i][k - 1][1] * dp[k + 1][j][1]
dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1]
return dp[0][n - 1][result]
在这个动态规划解法中，数组dp[i][j][0]和dp[i][j][1]应仅在i等于j时进行初始化，即仅初始化布尔值字符'0'和'1'的情况。对于非'0'和'1'的字符（即操作符'&', '|', '^'），它们在初始化时并不直接影响dp数组，因为它们不代表布尔值。初始化时，如果s[i]是'0'，则设置dp[i][i][0]为1；如果s[i]是'1'，则设置dp[i][i][1]为1。对于操作符位置的dp值，它们将在后续的动态规划过程中根据操作符两边的布尔表达式的值来计算更新。
在动态规划解法中，变量k用于表示操作符的位置，并且在每个子段的遍历中从i+1到j-1进行遍历。这样确保考虑了所有可能的操作符位置。变量k按照步长2遍历，因为操作符总是位于布尔值字符之间，即在两个布尔值字符的索引之间。这种遍历方式确保了所有可能的布尔表达式的分割方式都被考虑到，从而可以正确地计算出从i到j的结果为True或False的所有方法数。
题解中对于操作符'&'、'|'和'^'的处理逻辑已经覆盖了所有可能的操作组合。对于'&'操作符，它只有当两边结果都为True时，结果才为True；其它组合结果为False。对于'|'操作符，它当任意一边为True时结果为True，只有当两边都为False时结果才为False。对于'^'操作符，它当两边结果不相同时结果为True，当两边结果相同时结果为False。这些逻辑覆盖了所有可能的情况，因此没有遗漏。