Welcome to Subscribe On Youtube

1896. Minimum Cost to Change the Final Value of Expression

Description

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 is 1|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 to 0.

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:

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.

 

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 of expression).

Solution

Use stack and dynamic programming. Create three stacks to store the result values, the minimum number of operations, and the signs, respectively.

Loop over expression. For each position, calculate the value at the position and the minimum number of operations needed to change the value. When the loop ends, return the minimum cost to change the final value of expression.

  • class Solution {
    public int minOperationsToFlip(String expression) {
        Deque<Integer> numStack = new LinkedList<Integer>();
        Deque<Integer> opStack = new LinkedList<Integer>();
        Deque<Character> signStack = new LinkedList<Character>();
        int length = expression.length();
        for (int i = 0; i < length; i++) {
            char c = expression.charAt(i);
            if (Character.isDigit(c)) {
                numStack.push((int) (c - '0'));
                opStack.push(1);
            } else if (c == ')')
                signStack.pop();
            else {
                signStack.push(c);
                continue;
            }
            if (numStack.size() > 1 && signStack.peek() != '(') {
                int num2 = numStack.pop();
                int num1 = numStack.pop();
                int op2 = opStack.pop();
                int op1 = opStack.pop();
                char sign = signStack.pop();
                int[] ops = minOp(num1, num2, op1, op2, sign);
                numStack.push(ops[0]);
                opStack.push(ops[1]);
            }
        }
        return opStack.pop();
    }

    public int[] minOp(int num1, int num2, int op1, int op2, char sign) {
        if (sign == '&') {
            if (num1 == 1 && num2 == 1)
                return new int[]{1, Math.min(op1, op2)};
            else if (num1 == 0 && num2 == 0)
                return new int[]{0, Math.min(op1, op2) + 1};
            else
                return new int[]{0, 1};
        } else {
            if (num1 == 0 && num2 == 0)
                return new int[]{0, Math.min(op1, op2)};
            else if (num1 == 1 && num2 == 1)
                return new int[]{1, Math.min(op1, op2) + 1};
            else
                return new int[]{1, 1};
        }
    }
}

  • // OJ: https://leetcode.com/problems/minimum-cost-to-change-the-final-value-of-expression/
// Time: O(N)
// Space: O(N)
// Ref: https://www.bilibili.com/video/BV1yU4y1V79x
class Solution {
    stack<vector<int>> num;
    stack<char> op;
    void eval() {
        auto b = num.top(); num.pop();
        auto a = num.top(); num.pop();
        char c = op.top(); op.pop();
        if (c == '&') {
            num.push({
                min({ a[0] + b[0], a[1] + b[0], a[0] + b[1] }),
                min({ a[1] + b[1], a[1] + b[0] + 1, a[0] + b[1] + 1, a[1] + b[1] + 1 })
            });
        } else {
            num.push({
                min({ a[0] + b[0], a[0] + b[1] + 1, a[1] + b[0] + 1, a[0] + b[0] + 1 }),
                min({ a[1] + b[1], a[1] + b[0], a[0] + b[1] })
            });
        }
    }
public:
    int minOperationsToFlip(string s) {
        for (char c : s) {
            if (isdigit(c)) {
                if (c == '0') num.push({0, 1});
                else num.push({1, 0});
            } else if (c == '(') {
                op.push(c);
            } else if (c == ')') {
                while (op.top() != '(') eval();
                op.pop();
            } else {
                while (op.size() && op.top() != '(') eval();
                op.push(c);
            }
        }
        while (op.size()) eval();
        return max(num.top()[0], num.top()[1]);
    }
};

All Problems

All Solutions