Problem statement

https://leetcode.com/problems/minimum-cost-to-change-the-final-value-of-expression/

Solution

To solve this problem we need to understand that this is recursion problem. We need two things to make it work fast:

  1. For each closing bracket we need to find corresponding open bracket, we can do it with function corr with usual stack technique.

  2. We need to solve dp(beg, end) problem recursively. Here what this function will return is tuple (val, changes), where val is value before changing and changes is minumum number of changes we need to make to change val. There can be several different cases:

    2.1 We have structure like this ....?(...), where question mark can be either & or | and dots mean any symbols. Also it can happen that left dots are empty then we have case (...)

    2.2 We have string like this ...?n, where n can be either 0 or 1 and question mark is again | or &. Also it can happen that dots are empty than we have n case.

When we run dfs(beg, end) we need:

  1. Check if beg == end, then we have second case from case 2.2.
  2. If last symbol is digit, then we recursively run function for left and right parts.

  3. Also if last symbol is bracket and its corresponding symbol is starting brackets, then we have second case from 2.1 and we need to deal with it.

  4. Finally, what we have in the end, are two values p1, p2: true values for left and right parts and operation op. Here for simplicity I check all 8 possible case, this is exactly what I did on contest.
if p1 == 0 and p2 == 0 and op == "|": return (0, min(c1, c2))
if p1 == 1 and p2 == 0 and op == "|": return (1, 1)
if p1 == 1 and p2 == 1 and op == "|": return (1, 1 + min(c1, c2))
if p1 == 0 and p2 == 1 and op == "|": return (1, 1)
if p1 == 0 and p2 == 0 and op == "&": return (0, 1 + min(c1, c2))
if p1 == 1 and p2 == 0 and op == "&": return (0, 1)
if p1 == 1 and p2 == 1 and op == "&": return (1, min(c1, c2))
if p1 == 0 and p2 == 1 and op == "&": return (0, 1)

For example if we have 0|0, then what we can do is to change either left or right part to 1, so minimum number of changes is min(c1, c2). It can be written in shorter way, see code.

Complexity

Time complexity can be estimated as O(n), because in fact for every valid substring we have we will call it once. Space complexity is O(n) as well.

Code

class Solution:
    def minOperationsToFlip(self, E):
        def corr(s):
            stack, d = [], {}
            for i, elem in enumerate(s):
                if elem == "(":
                    stack.append(i)
                elif elem == ")":
                    last = stack.pop()
                    d[i] = last
            return d

        def dfs(beg, end):
            if beg == end: return (int(E[beg]) , 1)
            beg2 = d.get(end, end)
            if beg2 == beg: return dfs(beg + 1, end - 1)
            p1, c1 = dfs(beg, beg2 - 2)
            p2, c2 = dfs(beg2, end)
            op = E[beg2 - 1]
            
            t = {"|": lambda x, y:x|y, "&": lambda x, y:x&y}
            c3 = 1 if p1 + p2 == 1 else min(c1, c2) + (p1^(op == "&"))
            return (t[op](p1, p2), c3)
            
        d = corr(E)
        return dfs(0, len(E) - 1)[1]