Boolean Parenthesization

Time: O(n^3)

Space: O(n^2)

Intuition

DP on sub-expressions: dp_true[i][j] = number of ways substring [i,j] evaluates to TRUE; dp_false[i][j] = FALSE. Split at each operator k. Combine left and right using truth-table rules for AND, OR, XOR.

Algorithm

1Base: dp_true[i][i] = (sym[i]=="T") ? 1 : 0. dp_false[i][i] = 1 âˆ’ dp_true[i][i].
2For length l from 2 to n: for each (i,j): for each operator at k between i and j:
3 Compute lt,lf,rt,rf (left/right true/false counts).
4 AND: true += lt*rt. OR: true += lt*rt+lt*rf+lf*rt. XOR: true += lt*rf+lf*rt.
5 false = totalWays âˆ’ true.
6Return dp_true[0][n-1].

Example Walkthrough

Input: "T|T&F^T"

1.Symbols: T,T,F,T. Operators: |,&,^.
2.dp_true[0][3] = 4.

Output: 4

Common Pitfalls

•Total ways for a substring of length n = Catalan(n-1). Use it to compute false = total âˆ’ true.

Boolean Parenthesization.java

Java

// Approach: DP. dp[i][j][0/1] = number of ways to parenthesize s[i..j] to get false/true.
// Split at each operator and combine counts from left and right sub-expressions.
// Time: O(n^3) Space: O(n^2)
import java.util.*;

class Solution {
    static int countWays(String s) {
        int n = s.length();
        memo = new HashMap<>();

        return solve(s, 0, n - 1, true);
    }

    static Map<String, Integer> memo;

    static int solve(String s, int i, int j, boolean isTrue) {
        if (i > j)
            return 0;

        if (i == j) {
            if (isTrue) {
                if (s.charAt(i) == 'T')
                    return 1;
                else
                    return 0;
            } else {
                if (s.charAt(j) == 'F')
                    return 1;
                else
                    return 0;
            }
        }

        String key = i + "," + j + "," + isTrue + "";
        if (memo.containsKey(key))
            return memo.get(key);

        int ans = 0;

        for (int k = i + 1; k <= j - 1; k = k + 2) {
            int lT = solve(s, i, k - 1, true);
            int lF = solve(s, i, k - 1, false);
            int rT = solve(s, k + 1, j, true);
            int rF = solve(s, k + 1, j, false);

            if (s.charAt(k) == '&') {
                if (isTrue)
                    ans += (lT * rT);
                else
                    ans += (lT * rF) + (lF * rT) + (lF * rF);
            } else if (s.charAt(k) == '|') {
                if (isTrue)
                    ans += (lT * rF) + (lF * rT) + (lT * rT);
                else
                    ans += (lF * rF);
            } else if (s.charAt(k) == '^') {
                if (isTrue)
                    ans += (lT * rF) + (lF * rT);
                else
                    ans += (lT * rT) + (lF * rF);
            }
        }

        memo.put(key, ans);
        return ans;
    }
}

Was this solution helpful?