Q52 Boolean Evaluation - Coding Ninjas

import java.util.* ;
import java.io.*; 

public class Solution {
    public static long mod = (long)1e9+7;
    public static int evaluateExp(String str) {
        int n = str.length();
        return (int)solve(str , 0 ,n-1 ,1 , new Long[n+1][n+1][2]);

    }

    //memo -> (n*n*2)*n = n^3   |sc ->n*n*2 + n(height of stack)
    public static long solve(String str , int i , int j , int exp ,  Long[][][]dp ){
        if(i > j) return 0;

        //base case , for only one expression remains
        if(i == j){
            char ch = str.charAt(i);
            if(exp == 1)                //for true
            return ch == 'T' ? 1 : 0;   

            else                        //for false
            return ch == 'F' ? 1 : 0;
        }
        if(dp[i][j][exp] != null)
        return dp[i][j][exp];
        
        long ways = 0;
        for(int k = i+1 ; k <= j ;k+=2){
            //calls for no. of ways the left/right expression can be false(0) and true(1) (faith)
            long lt = solve(str , i , k-1 ,1 , dp);
            long rt = solve(str , k+1 , j , 1 ,dp);
            long lf = solve(str , i,k-1 , 0 , dp);
            long rf = solve(str , k+1 , j , 0 , dp);

            //checks no.of true false ways and return accordingly
            char ch = str.charAt(k);
            if(ch == '&'){
                //true ways
                if(exp == 1){
                    ways = (ways + (lt * rt)%mod)%mod;
                }
                //false ways
                else
                ways = (ways + (lf*rf)%mod + (lf*rt)%mod + (lt*rf)%mod)%mod;
            }
            else if(ch == '|'){
                if(exp == 1){
                    ways = (ways + (lt * rt)%mod + (lf*rt)%mod + (lt*rf)%mod)%mod;
                }
                else
                ways = (ways + (lf*rf)%mod)%mod;
            }
            else{       // ^ ways
                if(exp == 1){
                    ways = (ways + (lt * rf)%mod + (lf*rt)%mod)%mod;
                }
                else
                ways = (ways + (lf*rf)%mod + + (lt*rt)%mod)%mod;
            }
        }

        return dp[i][j][exp] = ways;
    }
}