Boolean Parenthesization Problem's code is not working

Question

Regarding the "Boolean Parenthesization" problem, my code doesn't work. I tried the approach using the dynamic approach, however for the the input of N=5 and T^F|F, I got 0 as the output but the correct output is 2.

I ran the following test cases:

For Input:

5
T^F|F

Your Output:

0

Expected Output:

2

I tried the following code:

class Solution {
    static int countWays(int N, String S) {
        int dp[][][] = new int[N][N][2];
        int mod = (int) 1e9;
        for (int i = 0; i < N; i++) {
            if (S.charAt(i) == 'T') {
                dp[i][i][1] = 1;
                dp[i][i][0] = 0;
            } else if (S.charAt(i) == 'F') {
                dp[i][i][1] = 0;
                dp[i][i][0] = 1;
            }
        }
        
        for (int i = N-1; i >= 0; i--) {
            for (int j = 0; j < N; j++) {
                for (int isTrue = 0; isTrue < 2; isTrue++) {
                    int ways = 0;

                    if (i > j)
                        continue;   
                    
                    for (int k = i+1; k < j; k += 2) {
                        int lt = dp[i][k-1][1];
                        int lf = dp[i][k-1][0];
                        int rt = dp[k+1][j][1];
                        int rf = dp[k+1][j][0];
                        
                        if (S.charAt(i) == '&') {
                            if (isTrue == 1) {
                                ways = (ways + lt*rt) % mod;
                            } else
                                ways = (ways + lt*rf + lf*rf + lf*rt) % mod;
                        } else if (S.charAt(i) == '|') {
                            if (isTrue == 1)
                                ways = (ways + lt*rt + lt*rf + lf*rt) % mod;
                            else
                                ways = (ways + lf*rf) % mod;
                        } else {
                            if (isTrue == 1)
                                ways = (ways + lt*rf + lf*rt) % mod;
                            else
                                ways = (ways + lt*rt + lf*rf) % mod;
                        }
                    }

                    dp[i][j][isTrue] = ways;
                }
            }
        }

        return dp[0][N-1][1];
    }
}

Answer 1

There are two bugs:

• if(S.charAt(i)=='&') is testing the wrong character. You want to test the character at the index k, not i. Same with the second comparison with '|'.

• if(i>j) continue; will allow the iteration to progress normally when i and j are equal, but that means that the inner loop with k will not run and that at the end of it, dp[i][j][isTrue] = ways; will always set dp[i][j][0] and dp[i][j][1] to zero, wiping out what you had put there in the initialisation part. So now all dp values will be zero before continuing with the accumulation of values. This will be fixed by doing if(i>=j) continue;

With those two fixes it will work. But still:

• It is a waste of time to have j iterate with values greater than (or equal to) i. Just start have it immediately start at a valid value, i+2.
• Have the loops on i and j increment with steps of 2, as the other indexes are irrelevant.
• Calculate the number of ways for false and true at the same moment, instead of looping with isTrue.

Here is adapted code:

    static int countWays(int N, String S) {
        int dp[][][] = new int[N][N][2];
        int mod = (int) 1e9;  // NB: on GeeksforGeeks this should be 1003

        for (int i = 0; i < N; i += 2) {
            dp[i][i][1] = S.charAt(i) == 'T' ? 1 : 0;
            dp[i][i][0] = 1 - dp[i][i][1];
        }
        
        for (int j = 0; j < N; j += 2) {
            for (int i = j - 2; i >= 0; i -= 2) {
                int waysTrue = 0;
                int waysTotal = 0; 
                for (int k = i + 1; k < j; k += 2) {
                    int lt = dp[i][k-1][1];
                    int lf = dp[i][k-1][0];
                    int rt = dp[k+1][j][1];
                    int rf = dp[k+1][j][0];
                    int ff = (lf * rf) % mod;
                    int ft = (lf * rt) % mod;
                    int tf = (lt * rf) % mod;
                    int tt = (lt * rt) % mod;
                    char ch = S.charAt(k);
                    waysTotal += ff + ft + tf + tt;
                    waysTrue += ch == '&' ? tt
                              : ch == '|' ? ft + tf + tt
                              : ch == '^' ? ft + tf;
                }
                dp[i][j][1] = waysTrue % mod;
                dp[i][j][0] = (waysTotal - waysTrue) % mod;
            }
        }
        return dp[0][N-1][1];
    }