Print all balanced bracket strings formed by replacing the wildcard character '?'

Balanced brackets means that if we have a string of brackets, then each open bracket has a corresponding closing bracket, and the bracket pairs are nested correctly. The size of the string should be an even number. In this problem, we are given a bracket string containing the character '?' and our task is to form every possible balanced bracket string by replacing '?' with the appropriate bracket. In our given string, only parentheses '(' and ')' are used.

ExampleExample

Input 1: str = “()(?)?”
Output 1: ()(())

The Chinese translation of

Explanation

is:

Explanation

Only a balanced string can be formed by replacing '?'.

Input 2: str = “??????”

Output 2: ((()))
(()())
(())()
()(())
()()()

The Chinese translation of

Explanation

is:

Explanation

There are two possible ways to form a balanced string.

• One way is to replace indices 0, 1 and 2 with an open bracket and the other indices with a closed bracket.

• The second method is to replace indices 0, 1, and 3 with an open bracket, and the other indices with a closed bracket.

• The third method is to replace indexes 0, 1 and 4 with open brackets and the other indices with closed brackets.

• The fourth method is to replace the positions at index 0, 2 and 3 with an open bracket and replace the positions at other indexes with a closed bracket.

• The last way is to replace indexes 0, 2 and 4 with open brackets and the other indexes with closed brackets.

method

We have seen the example of the given string above, let’s move on to the next step -

We can use the backtracking method to solve this problem.

Let us discuss this method below -

• First, we will initialize a function called 'create' to create all possible strings after replacing '?' with brackets, with parameters str and index = 0.

• In this function,

−> First, we set the basic conditions. If we reach the end of the string, then we must pass the string to the "check" function to verify that the string is balanced. If it is balanced, print the string.

−>If the current character of the string is ‘?’,

First, replace it with an open bracket and call the same function to check if the end of the string is reached.

Secondly, replace it with the closing bracket and call the same function again to check if we have reached the end of the string.

Finally, we backtrack the string and assign the current character to ‘?’

−> Otherwise, if the current character of the string is a bracket, move to the next index by calling the same function.

• Initialize the 'check' function to verify that the string is balanced.

−> In this function, we initialize the stack and then check

−> If the first character of the string is a closing bracket, return false

−> If the current bracket is closed, there are two situations: if the stack is empty, false is returned because there is no corresponding open bracket. Otherwise, pop the corresponding open bracket from the stack.

−> Finally, we check whether the stack is empty. If it is empty, it means the string is balanced and returns true. Otherwise, there are some brackets remaining, which means the string is unbalanced and returns false.

The Chinese translation of

Example

is:

Example

The following is the C code used for the above backtracking method to obtain all balanced strings

#include <bits/stdc++.h>
using namespace std;
// Function 'check' to verify whether the string is balanced or not
bool check(string str){
   stack<char> S; // created stack

// If the first character of the string is a close bracket, then return false
   if (str[0] == ')') {
      return false;
   }

   // Traverse the string using for loop
   for (int i = 0; i < str.size(); i++) {

      // If the current character is an open bracket, then push it into the stack
      if (str[i] == '(') {
         S.push('(');
      }

      // If the current character is a close bracket
      else {

         // If the stack is empty, there is no corresponding open bracket return false
         if (S.empty()){
            return false;
         }

         // Else pop the corresponding opening bracket from the stack
         else
            S.pop();
      }
   }

   // If the stack is empty, return true
   if (S.empty()){
      return true;
   }
   else {
      return false;
   }
}

// Function 'create' to create all possible bracket strings
void create(string str, int i){

   // If reached the end of the string
   if (i == str.size()) {

      // passed 'str' to the 'check' function to verify whether the string is balanced or not
      if (check(str)) {

         // If it is a balanced string
         cout<< str << endl; // print the string
      }
      return;
   }

   // If the current character of the string is '?'
   if (str[i] == '?') {
      str[i] = '('; // replace ? with (
      create(str, i + 1); // continue to next character
      str[i] = ')'; // replace ? with )
      create(str, i + 1); // continue to next character

      // backtrack
      str[i] = '?';
   }

   // If the current character is bracketed then move to the next index
   else {
      create(str, i + 1);
   }
}
int main(){
   string str = "??????"; //given string

   // Call the function
   create (str, 0);
   return 0;
}

Output

((()))
(()())
(())()
()(())
()()()

Time complexity and space complexity

The time complexity of the above code is O(N*(2^N)) because we need to backtrack on the string.

The space complexity of the above code is O(N) because we store the brackets on the stack.

Where N is the size of the string.

in conclusion

In this tutorial, we implemented a program that prints all balanced bracket strings that can be formed by replacing the wildcard character '?'. We implemented a backtracking method. The time complexity is O(N*(2^N), and the space complexity is O(N). Where N is the size of the string.

The above is the detailed content of Print all balanced bracket strings formed by replacing the wildcard character '?'. For more information, please follow other related articles on the PHP Chinese website!