給定一個布爾表達式和一個期望的布爾結果 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 個
一、記憶化遞歸
lru_cache可以記錄函數的調用結果。
根據結果分類:
result = 1: 0&0 + 0&1 + 1&0/0|0/ 1^1
result = 0: 1&1/1|1 + 0|1 + 1|0/1^ 0 + 0^1
Class Solution:
AND = '&'
OR = '|'
XOR = '^'
@lru_cache(None)
def countEval(self, s: str, result: int) -> int:
if len(s) <= 3:
return int(eval(s) == result)
res = 0
for i in range(1, len(s), 2):
symbol = s[i]
if result == 0:
if symbol == self.AND:
# 0&0 + 0&1 + 1&0
res += self.countEval(s[:i], 0)*self.countEval(s[i+1:], 0) + self.countEval(s[:i], 0)*self.countEval(s[i+1:], 1) + self.countEval(s[:i], 1)*self.countEval(s[i+1:], 0)
elif symbol == self.OR:
# 0|0
res += self.countEval(s[:i], 0)*self.countEval(s[i+1:], 0)
elif symbol == self.XOR:
# 0^0 + 1^1
res += self.countEval(s[:i], 0)*self.countEval(s[i+1:], 0) + self.countEval(s[:i], 1)*self.countEval(s[i+1:], 1)
else:
if symbol == self.AND:
# 1&1
res += self.countEval(s[:i], 1)*self.countEval(s[i+1:], 1)
elif symbol == self.OR:
# 1|1 + 0|1 + 1|0
res += self.countEval(s[:i], 1)*self.countEval(s[i+1:], 1) + self.countEval(s[:i], 0)*self.countEval(s[i+1:], 1) + self.countEval(s[:i], 1)*self.countEval(s[i+1:], 0)
elif symbol == self.XOR:
# 1^0 + 0^1
res += self.countEval(s[:i], 1)*self.countEval(s[i+1:], 0) + self.countEval(s[:i], 0)*self.countEval(s[i+1:], 1)
return int(res)