Minimum Cost to Change the Final Value of Expression LeetCode solution in Python

1
class Solution:
2
    def minOperationsToFlip(self, expression: str) -> int:
3
        loc = {}
4
        stack = []
5
        for i in reversed(range(len(expression))):
6
            if expression[i] == ")":
7
                stack.append(i)
8
            elif expression[i] == "(":
9
                loc[stack.pop()] = i
10

11
        def fn(lo, hi):
12
            """Return value and min op to change value."""
13
            if lo == hi:
14
                return int(expression[lo]), 1
15
            if expression[hi] == ")" and loc[hi] == lo:
16
                return fn(lo + 1, hi - 1)  # strip parenthesis
17
            mid = loc.get(hi, hi) - 1
18
            v, c = fn(mid + 1, hi)
19
            vv, cc = fn(lo, mid - 1)
20
            if expression[mid] == "|":
21
                val = v | vv
22
                if v == vv == 0:
23
                    chg = min(c, cc)
24
                elif v == vv == 1:
25
                    chg = 1 + min(c, cc)
26
                else:
27
                    chg = 1
28
            else:  # expression[k] == "&"
29
                val = v & vv
30
                if v == vv == 0:
31
                    chg = 1 + min(c, cc)
32
                elif v == vv == 1:
33
                    chg = min(c, cc)
34
                else:
35
                    chg = 1
36
            return val, chg
37

38
        return fn(0, len(expression) - 1)[1]