Boolean Parenthesization

Given a boolean expression S of length N with following symbols.

Symbols

• ‘T’ —-> true
• ‘F’ —-> false

and following operators filled between symbols

Operators

• & —-> boolean AND
• | —-> boolean OR
• ^ —-> boolean XOR

Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.

• Time : O(n^3)
  • each l to r range requires r - l times operation
  • so complexity is n n n
• Space : O(n^2)

class Solution{
    unordered_map<char, function<bool(bool,bool)>> mp;
    int dp[201][201][2]; //number of operations
    int mod = 1e3 + 3;
    int helper(string& s, int l, int r, bool t) {
        if(dp[l][r][t] != -1) return dp[l][r][t];
        if(l == r) {
            bool exp = s[l] == 'T';
            return dp[l][r][t] = exp == t;
        }
        if(l + 2 == r) {
            bool expA = s[l] == 'T', expB = s[r] == 'T';
            bool exp = mp[s[l + 1]](expA, expB);
            return dp[l][r][t] = exp == t;
        }
        int& res = dp[l][r][t] = 0;
        for(int i = l + 1; i < r; i += 2) {
            char op = s[i];
            switch(op) {
                case '&': 
                    if(t) {
                        res += helper(s, l, i - 1, true) * helper(s, i + 1, r, true);
                    } else {
                        res += helper(s, l, i - 1, true) * helper(s, i + 1, r, false);
                        res += helper(s, l, i - 1, false) * helper(s, i + 1, r, true);
                        res += helper(s, l, i - 1, false) * helper(s, i + 1, r, false);
                    }
                    break;
                case '|': 
                    if(t) {
                        res += helper(s, l, i - 1, true) * helper(s, i + 1, r, true);
                        res += helper(s, l, i - 1, true) * helper(s, i + 1, r, false);
                        res += helper(s, l, i - 1, false) * helper(s, i + 1, r, true);
                    } else {
                        res += helper(s, l, i - 1, false) * helper(s, i + 1, r, false);
                    }
                    break;
                case '^': 
                    if(t) {
                        res += helper(s, l, i - 1, true) * helper(s, i + 1, r, false);
                        res += helper(s, l, i - 1, false) * helper(s, i + 1, r, true);
                    } else {
                        res += helper(s, l, i - 1, true) * helper(s, i + 1, r, true);
                        res += helper(s, l, i - 1, false) * helper(s, i + 1, r, false);
                    }
                    break;
                default: break;
            }
            res = res % mod;
        }
        
        return res;
    }
public:
    int countWays(int N, string S){
        memset(dp, -1, sizeof dp);
        auto AND = [](bool a, bool b) {return a & b;};
        auto OR = [](bool a, bool b) {return a | b;};
        auto XOR = [](bool a, bool b) {return a ^ b;};
        mp['&'] = AND;
        mp['|'] = OR;
        mp['^'] = XOR;
        return helper(S, 0, N - 1, true);
    }
};