#1896
Minimum Cost to Change the Final Value of Expression
candidate master · 1410 · lc hard +32 · failed · 51.2% accepted · 248 likes · top 40%
Description
You are given a valid boolean expression string expression using '1', '0', '&', '|', '(', and ')'. Evaluate left to right inside each pair of parentheses.
In one operation, change any single character (flip a bit, or change '&' to '|' or vice versa).
Return the minimum number of operations to flip the overall value of expression.
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:
Input: expression = "(0&0)&(0&0&0)"
Output: 3
Explanation: We can turn "(0&0)&(0&0&0)" into "(0|1)|(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.
Code
1
2
3