Number of balanced bracket expressions that can be formed from a string
Given a string str comprising of characters (, ), {, }, [, ] and ?. The task is to find the total number of balanced bracket expressions formed when ? can be replaced with any of the bracket characters.
Here are some examples of balanced bracket expressions: {([])}, {()}[{}] etc.
And, unbalanced bracket expressions: {[}, {()], {()}[) etc.
Examples:
Input: str = “(?([?)]?}?”
Output: 3
({([()]]}), ()([()]{}) and ([([])]{}) are the only possible balanced expressions that can be generated from the input.Input: str = “???[???????]????”
Output: 392202
Approach:
- If n is odd, then the result will always be 0 as there will be no balanced expression possible.
- If n id even, then create a dp array for storing precomputations.
- Call a recursive function with the following operations:
- If starting index > ending index then you return 1.
- If dp[start][end] is already computed, return dp[start][end].
- Run a loop from start + 1 till end incrementing by 2 to find its pair bracket or ‘?’.
- Then divide the string into two halves to check to proper subsequent bracket expressions from start + 1 till i – 1 and i + 1 till the end by calling the recursive function.
- If st[start] = ’?’ and st[i] = ’?’ then a total of 3 combinations of bracket pairs can be formed, thus multiplying the result of the recursive function by 3.
- Return dp[start][end]
Below is the implementation of the above approach:
C++
// C++ program to find number of balanced// bracket expressions possible#include <bits/stdc++.h>using namespace std;typedef long long int lli;// Max string lengthconst int MAX = 300;// Function to check whether index start// and end can form a bracket pair or notint checkFunc(int i, int j, string st){ // Check for brackets ( ) if (st[i] == '(' && st[j] == ')') return 1; if (st[i] == '(' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ')') return 1; // Check for brackets [ ] if (st[i] == '[' && st[j] == ']') return 1; if (st[i] == '[' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ']') return 1; // Check for brackets { } if (st[i] == '{' && st[j] == '}') return 1; if (st[i] == '{' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == '}') return 1; return 0;}// Function to find number of// proper bracket expressionsint countRec(int start, int end, int dp[][MAX], string st){ int sum = 0; // If starting index is greater // than ending index if (start > end) return 1; // If dp[start][end] has already been computed if (dp[start][end] != -1) return dp[start][end]; lli i, r = 0; // Search for the bracket in from next index for (i = start + 1; i <= end; i += 2) { // If bracket pair is formed, // add number of combination if (checkFunc(start, i, st)) { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st); } // If ? comes then all three bracket // expressions are possible else if (st[start] == '?' && st[i] == '?') { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st) * 3; } } // Return answer return dp[start][end] = sum;}int countWays(string st){ int n = st.length(); // If n is odd, string cannot be balanced if (n % 2 == 1) return 0; int dp[MAX][MAX]; memset(dp, -1, sizeof(dp)); return countRec(0, n - 1, dp, st);}// Driving functionint main(){ string st = "(?([?)]?}?"; cout << countWays(st); return 0;} |
Java
// Java program to find number of balanced// bracket expressions possibleclass GFG { // Max string length static int MAX = 300; // Function to check whether index start // and end can form a bracket pair or not static int checkFunc(int i, int j, String st) { // Check for brackets ( ) if (st.charAt(i) == '(' && st.charAt(j) == ')') return 1; if (st.charAt(i) == '(' && st.charAt(j) == '?') return 1; if (st.charAt(i) == '?' && st.charAt(j) == ')') return 1; // Check for brackets [ ] if (st.charAt(i) == '[' && st.charAt(j) == ']') return 1; if (st.charAt(i) == '[' && st.charAt(j) == '?') return 1; if (st.charAt(i) == '?' && st.charAt(j) == ']') return 1; // Check for brackets { } if (st.charAt(i) == '{' && st.charAt(j) == '}') return 1; if (st.charAt(i) == '{' && st.charAt(j) == '?') return 1; if (st.charAt(i) == '?' && st.charAt(j) == '}') return 1; return 0; } // Function to find number of // proper bracket expressions static int countRec(int start, int end, int dp[][], String st) { int sum = 0; // If starting index is greater // than ending index if (start > end) return 1; // If dp[start][end] has already been computed if (dp[start][end] != -1) return dp[start][end]; int i, r = 0; // Search for the bracket in from next index for (i = start + 1; i <= end; i += 2) { // If bracket pair is formed, // add number of combination if (checkFunc(start, i, st) == 1) { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st); } // If ? comes then all three bracket // expressions are possible else if (st.charAt(start) == '?' && st.charAt(i) == '?') { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st) * 3; } } // Return answer return dp[start][end] = sum; } static int countWays(String st) { int n = st.length(); // If n is odd, string cannot be balanced if (n % 2 == 1) return 0; int dp[][] = new int[MAX][MAX]; for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) dp[i][j] = -1; return countRec(0, n - 1, dp, st); } // Driving function public static void main(String[] args) { String st = "(?([?)]?}?"; System.out.println(countWays(st)); }}// This code is contributed by ihritik |
Python 3
# Python 3 program to find number of balanced# bracket expressions possible# Max string lengthMAX = 300# Function to check whether index start# and end can form a bracket pair or notdef checkFunc(i, j, st): # Check for brackets ( ) if (st[i] == '(' and st[j] == ')'): return 1 if (st[i] == '(' and st[j] == '?'): return 1 if (st[i] == '?' and st[j] == ')'): return 1 # Check for brackets [ ] if (st[i] == '[' and st[j] == ']'): return 1 if (st[i] == '[' and st[j] == '?'): return 1 if (st[i] == '?' and st[j] == ']'): return 1 # Check for brackets { } if (st[i] == '{' and st[j] == '}'): return 1 if (st[i] == '{' and st[j] == '?'): return 1 if (st[i] == '?' and st[j] == '}'): return 1 return 0# Function to find number of# proper bracket expressionsdef countRec(start, end, dp, st): sum = 0 # If starting index is greater # than ending index if (start > end): return 1 # If dp[start][end] has already # been computed if (dp[start][end] != -1): return dp[start][end] r = 0 # Search for the bracket in from next index for i in range(start + 1, end + 1, 2): # If bracket pair is formed, # add number of combination if (checkFunc(start, i, st)): sum = (sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st)) # If ? comes then all three bracket # expressions are possible elif (st[start] == '?' and st[i] == '?'): sum = (sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st) * 3) # Return answer dp[start][end] = sum return dp[start][end]def countWays( st): n = len(st) # If n is odd, string cannot be balanced if (n % 2 == 1): return 0 dp = [[-1 for i in range(MAX)] for i in range(MAX)] return countRec(0, n - 1, dp, st)# Driver Codeif __name__ =="__main__": st = "(?([?)]?}?" print(countWays(st))# This code is contributed by ita_c |
C#
// C# program to find number of balanced// bracket expressions possibleusing System;class GFG { // Max string length static int MAX = 300; // Function to check whether index start // and end can form a bracket pair or not static int checkFunc(int i, int j, string st) { // Check for brackets ( ) if (st[i] == '(' && st[j] == ')') return 1; if (st[i] == '(' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ')') return 1; // Check for brackets [ ] if (st[i] == '[' && st[j] == ']') return 1; if (st[i] == '[' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ']') return 1; // Check for brackets { } if (st[i] == '{' && st[j] == '}') return 1; if (st[i] == '{' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == '}') return 1; return 0; } // Function to find number of // proper bracket expressions static int countRec(int start, int end, int[, ] dp, string st) { int sum = 0; // If starting index is greater // than ending index if (start > end) return 1; // If dp[start, end] has already been computed if (dp[start, end] != -1) return dp[start, end]; int i; // Search for the bracket in from next index for (i = start + 1; i <= end; i += 2) { // If bracket pair is formed, // add number of combination if (checkFunc(start, i, st) == 1) { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st); } // If ? comes then all three bracket // expressions are possible else if (st[start] == '?' && st[i] == '?') { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st) * 3; } } // Return answer return dp[start, end] = sum; } static int countWays(string st) { int n = st.Length; // If n is odd, string cannot be balanced if (n % 2 == 1) return 0; int[, ] dp = new int[MAX, MAX]; for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) dp[i, j] = -1; return countRec(0, n - 1, dp, st); } // Driving function public static void Main() { string st = "(?([?)]?}?"; Console.WriteLine(countWays(st)); }}// This code is contributed by ihritik |
Javascript
<script>// Javascript program to find number of balanced// bracket expressions possible // Max string length let MAX = 300; // Function to check whether index start // and end can form a bracket pair or not function checkFunc(i,j,st) { // Check for brackets ( ) if (st[i] == '(' && st[j] == ')') return 1; if (st[i] == '(' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ')') return 1; // Check for brackets [ ] if (st[i] == '[' && st[j] == ']') return 1; if (st[i] == '[' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ']') return 1; // Check for brackets { } if (st[i] == '{' && st[j] == '}') return 1; if (st[i] == '{' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == '}') return 1; return 0; } // Function to find number of // proper bracket expressions function countRec(start,end,dp,st) { let sum = 0; // If starting index is greater // than ending index if (start > end) return 1; // If dp[start][end] has already been computed if (dp[start][end] != -1) return dp[start][end]; let i, r = 0; // Search for the bracket in from next index for (i = start + 1; i <= end; i += 2) { // If bracket pair is formed, // add number of combination if (checkFunc(start, i, st) == 1) { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st); } // If ? comes then all three bracket // expressions are possible else if (st[start] == '?' && st[i] == '?') { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st) * 3; } } // Return answer return dp[start][end] = sum; } function countWays(st) { let n = st.length; // If n is odd, string cannot be balanced if (n % 2 == 1) return 0; let dp = new Array(MAX); for (let i = 0; i < MAX; i++) { dp[i]=new Array(MAX); for (let j = 0; j < MAX; j++) dp[i][j] = -1; } return countRec(0, n - 1, dp, st); } // Driving function let st = "(?([?)]?}?"; document.write(countWays(st)); // This code is contributed by rag2127</script> |
Output:
3
Time Complexity: O(N^3)
Auxiliary Space: O(MAX^2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
