Print all Balanced Brackets Strings that can be formed by replacing wild card β?β
Given string str containing characters β?β, β(β and β)β, the task is to replace the β?β character with β(β or β)β and print all the strings containing balanced brackets
Example:
Input: str = β????β
Output:
()()
(())Input: str = β(()?β
Output: (())
Approach: The given problem can be solved using recursion and backtracking. The idea is to substitute every β?β character with β)β then make a recursive call to the next index and after backtracking change it to β(β then make a recursive call to the next index, after backtracking change the character back to β?β. Follow the steps below to solve the problem:
- Convert the string str into a character array, say ch
- Pass the character array ch and index 0 as parameters inside recursive function and at every recursive call perform the following:
- If the index becomes equal to the length of the character array the:
- Check if the character array is a balanced bracket string
- If the above condition is true then print the string
- If the current character ch[index] is either β(β or β)β then make a recursive call on the next index
- If the current character ch[index] is β?β then:
- Replace it with β(β and make a recursive call on the next index
- Replace it with β)β and make a recursive call on the next index
- Change it back to β?β before returning from the function
- If the index becomes equal to the length of the character array the:
Below is the implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the // characters of the string void print(string ch) { for ( char c : ch) { cout << c; } cout << endl; } // Function to check if the // brackets are valid or not bool check(string ch) { // Initialize a stack stack< char > S; // If character is an open bracket // then return false if (ch[0] == ')' ) { return false ; } // Iterate the character array for ( int i = 0; i < ch.length(); i++) { // If character is an open bracket // then push it in the stack if (ch[i] == '(' ) { S.push( '(' ); } // If character is a close bracket else { // If stack is empty, there is no // corresponding opening bracket // so return false if (S.size() == 0) return false ; // Else pop the corresponding // opening bracket from the stack else S.pop(); } } // If no opening bracket remains // then return true if (S.size() == 0) return true ; // If there are opening brackets // then return false else return false ; } // Function to find number of // strings having balanced brackets void count(string ch, int index) { // Reached end of character array if (index == ch.length()) { // Check if the character array // contains balanced string if (check(ch)) { // If it is a balanced string // then print its characters print(ch); } return ; } if (ch[index] == '?' ) { // replace ? with ( ch[index] = '(' ; count(ch, index + 1); // replace ? with ) ch[index] = ')' ; count(ch, index + 1); // backtrack ch[index] = '?' ; } else { // If current character is a // valid bracket then continue // to the next character count(ch, index + 1); } } // Driver function int main() { string ch = "????" ; // Call the function count(ch, 0); return 0; } // This code is contributed by Potta Lokesh |
Java
// Java implementation for the above approach import java.io.*; import java.util.*; class Main { // Function to print the // characters of the string static void print( char ch[]) { for (Character c : ch) { System.out.print(c); } System.out.println(); } // Function to check if the // brackets are valid or not static boolean check( char ch[]) { // Initialize a stack Stack<Character> S = new Stack<>(); // If character is an open bracket // then return false if (ch[ 0 ] == ')' ) { return false ; } // Iterate the character array for ( int i = 0 ; i < ch.length; i++) { // If character is an open bracket // then push it in the stack if (ch[i] == '(' ) { S.add( '(' ); } // If character is a close bracket else { // If stack is empty, there is no // corresponding opening bracket // so return false if (S.size() == 0 ) return false ; // Else pop the corresponding // opening bracket from the stack else S.pop(); } } // If no opening bracket remains // then return true if (S.size() == 0 ) return true ; // If there are opening brackets // then return false else return false ; } // Function to find number of // strings having balanced brackets static void count( char ch[], int index) { // Reached end of character array if (index == ch.length) { // Check if the character array // contains balanced string if (check(ch)) { // If it is a balanced string // then print its characters print(ch); } return ; } if (ch[index] == '?' ) { // replace ? with ( ch[index] = '(' ; count(ch, index + 1 ); // replace ? with ) ch[index] = ')' ; count(ch, index + 1 ); // backtrack ch[index] = '?' ; } else { // If current character is a // valid bracket then continue // to the next character count(ch, index + 1 ); } } // Driver function public static void main(String[] args) { String m = "????" ; char ch[] = m.toCharArray(); // Call the function count(ch, 0 ); } } |
Python3
# Python code for the above approach # Function to print the # characters of the string def printf(ch): for c in ch: print (c, end = ""); print (""); # Function to check if the # brackets are valid or not def check(ch): # Initialize a stack S = []; # If character is an open bracket # then return false if (ch[ 0 ] = = ')' ): return False ; # Iterate the character array for i in range ( len (ch)): # If character is an open bracket # then push it in the stack if (ch[i] = = '(' ): S.append( '(' ); # If character is a close bracket else : # If stack is empty, there is no # corresponding opening bracket # so return false if ( len (S) = = 0 ): return False ; # Else pop the corresponding # opening bracket from the stack else : S.pop(); # If no opening bracket remains # then return true if ( len (S) = = 0 ): return True ; # If there are opening brackets # then return false else : return False ; # Function to find number of # strings having balanced brackets def count(ch, index): # Reached end of character array if (index = = len (ch)): # Check if the character array # contains balanced string if (check(ch)): # If it is a balanced string # then print its characters printf(ch); return ; if (ch[index] = = '?' ): # replace ? with ( ch[index] = '(' ; count(ch, index + 1 ); # replace ? with ) ch[index] = ')' ; count(ch, index + 1 ); # backtrack ch[index] = '?' ; else : # If current character is a # valid bracket then continue # to the next character count(ch, index + 1 ); # Driver function ch = "????" ; # Call the function count( list (ch), 0 ); # This code is contributed by Saurabh Jaiswal |
C#
// C# implementation for the above approach using System; using System.Collections; public class Gfg{ // Function to print the // characters of the string static void print( char []ch) { foreach ( char c in ch) { Console.Write(c); } Console.WriteLine(); } // Function to check if the // brackets are valid or not static bool check( char []ch) { // Initialize a stack Stack S = new Stack(); // If character is an open bracket // then return false if (ch[0] == ')' ) { return false ; } // Iterate the character array for ( int i = 0; i < ch.Length; i++) { // If character is an open bracket // then push it in the stack if (ch[i] == '(' ) { S.Push( '(' ); } // If character is a close bracket else { // If stack is empty, there is no // corresponding opening bracket // so return false if (S.Count == 0) return false ; // Else pop the corresponding // opening bracket from the stack else S.Pop(); } } // If no opening bracket remains // then return true if (S.Count == 0) return true ; // If there are opening brackets // then return false else return false ; } // Function to find number of // strings having balanced brackets static void count( char []ch, int index) { // Reached end of character array if (index == ch.Length) { // Check if the character array // contains balanced string if (check(ch)) { // If it is a balanced string // then print its characters print(ch); } return ; } if (ch[index] == '?' ) { // replace ? with ( ch[index] = '(' ; count(ch, index + 1); // replace ? with ) ch[index] = ')' ; count(ch, index + 1); // backtrack ch[index] = '?' ; } else { // If current character is a // valid bracket then continue // to the next character count(ch, index + 1); } } // Driver function public static void Main( string [] args) { string m = "????" ; char []ch = m.ToCharArray(); // Call the function count(ch, 0); } } // This code is contributed by AnkThon |
Javascript
<script> // Javascript code for the above approach // Function to print the // characters of the string function printf(ch) { for (c of ch) { document.write(c); } document.write( "<br>" ); } // Function to check if the // brackets are valid or not function check(ch) { // Initialize a stack let S = []; // If character is an open bracket // then return false if (ch[0] == ')' ) { return false ; } // Iterate the character array for (let i = 0; i < ch.length; i++) { // If character is an open bracket // then push it in the stack if (ch[i] == '(' ) { S.push( '(' ); } // If character is a close bracket else { // If stack is empty, there is no // corresponding opening bracket // so return false if (S.length == 0) return false ; // Else pop the corresponding // opening bracket from the stack else S.pop(); } } // If no opening bracket remains // then return true if (S.length == 0) return true ; // If there are opening brackets // then return false else return false ; } // Function to find number of // strings having balanced brackets function count(ch, index) { // Reached end of character array if (index == ch.length) { // Check if the character array // contains balanced string if (check(ch)) { // If it is a balanced string // then print its characters printf(ch); } return ; } if (ch[index] == '?' ) { // replace ? with ( ch[index] = '(' ; count(ch, index + 1); // replace ? with ) ch[index] = ')' ; count(ch, index + 1); // backtrack ch[index] = '?' ; } else { // If current character is a // valid bracket then continue // to the next character count(ch, index + 1); } } // Driver function let ch = "????" ; // Call the function count(ch.split( "" ), 0); // This code is contributed by Saurabh Jaiswal </script> |
Output
(()) ()()
Time Complexity: O(N*2^N)
Auxiliary Space: O(N)