You are given a valid boolean expression as a string expression
consisting of the characters '1'
,'0'
,'&'
(bitwise AND operator),'|'
(bitwise OR operator),'('
, and ')'
.
- For example,
"()1|1"
and"(1)&()"
are not valid while"1"
,"(((1))|(0))"
, and"1|(0&(1))"
are valid expressions.
Return the minimum cost to change the final value of the expression.
- For example, if
expression = "1|1|(0&0)&1"
, its value is1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1
. We want to apply operations so that the new expression evaluates to0
.
The cost of changing the final value of an expression is the number of operations performed on the expression. The types of operations are described as follows:
- Turn a
'1'
into a'0'
. - Turn a
'0'
into a'1'
. - Turn a
'&'
into a'|'
. - Turn a
'|'
into a'&'
.
Note: '&'
does not take precedence over '|'
in the order of calculation. Evaluate parentheses first, then in left-to-right order.
Example 1:
Input: expression = "1&(0|1)" Output: 1 Explanation: We can turn "1&(0|1)" into "1&(0&1)" by changing the '|' to a '&' using 1 operation. The new expression evaluates to 0.
Example 2:
1 2 3 4 |
<strong>Input:</strong> expression = "(0&0)&(0&0&0)" <strong>Output:</strong> 3 <strong>Explanation:</strong> We can turn "(0<strong>&0</strong>)<strong><u>&</u></strong>(0&0&0)" into "(0<strong>|1</strong>)<strong>|</strong>(0&0&0)" using 3 operations. The new expression evaluates to 1. |
Example 3:
Input: expression = "(0|(1|0&1))" Output: 1 Explanation: We can turn "(0|(1|0&1))" into "(0|(0|0&1))" using 1 operation. The new expression evaluates to 0.
Constraints:
1 <= expression.length <= 105
expression
only contains'1'
,'0'
,'&'
,'|'
,'('
, and')'
- All parentheses are properly matched.
- There will be no empty parentheses (i.e:
"()"
is not a substring ofexpression
).
Solution: DP, Recursion / Simulation w/ Stack
For each expression, stores the min cost to change value to 0 and 1.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution { public: int minOperationsToFlip(string expression) { stack<array<int, 3>> s; s.push({0, 0, 0}); for (char e : expression) { if (e == '(') s.push({0, 0, 0}); else if (e == '&' || e == '|') s.top()[2] = e; else { if (isdigit(e)) s.push({e != '0', e != '1', 0}); auto [r0, r1, _] = s.top(); s.pop(); auto [l0, l1, op] = s.top(); s.pop(); if (op == '&') { s.push({min(l0, r0), min(l1 + r1, min(l1, r1) + 1), 0}); } else if (op == '|') { s.push({min(l0 + r0, min(l0, r0) + 1), min(l1, r1), 0}); } else { s.push({r0, r1, 0}); } } } return max(s.top()[0], s.top()[1]); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment