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 stringvoid print(string ch){ for (char c : ch) { cout << c; } cout << endl;}// Function to check if the// brackets are valid or notbool 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 bracketsvoid 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 functionint main(){ string ch = "????"; // Call the function count(ch, 0); return 0;}// This code is contributed by Potta Lokesh |
Java
// Java implementation for the above approachimport 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 stringdef printf(ch): for c in ch: print(c, end=""); print("");# Function to check if the# brackets are valid or notdef 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 bracketsdef 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 functionch = "????";# Call the functioncount(list(ch), 0);# This code is contributed by Saurabh Jaiswal |
C#
// C# implementation for the above approachusing 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 stringfunction printf(ch) { for (c of ch) { document.write(c); } document.write("<br>");}// Function to check if the// brackets are valid or notfunction 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 bracketsfunction 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 functionlet ch = "????";// Call the functioncount(ch.split(""), 0);// This code is contributed by Saurabh Jaiswal</script> |
Output
(()) ()()
Time Complexity: O(N*2^N)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
