Imprima todas las strings de corchetes equilibrados que se pueden formar reemplazando el comodín ‘?’

Dada la string str que contiene los caracteres ‘?’, ‘(‘ y ‘)’, la tarea es reemplazar el ‘?’ carácter con ‘(‘ o ‘)’ e imprime todas las strings que contienen corchetes balanceados

Ejemplo:

Entrada: str = “????”
Salida:
()()
(())

Entrada: str = “(()?”
Salida: (())

Enfoque: El problema dado se puede resolver usando recursividad y retroceso . La idea es sustituir cada ‘?’ carácter con ‘)’ luego haga una llamada recursiva al siguiente índice y después de retroceder cámbielo a ‘(‘ luego haga una llamada recursiva al siguiente índice, después de retroceder cambie el carácter a ‘?’ . Siga los pasos a continuación para resolver el problema:

• Convierta la string str en una array de caracteres , digamos ch
• Pase la array de caracteres ch y el índice 0 como parámetros dentro de la función recursiva y en cada llamada recursiva realice lo siguiente:
  • Si el índice se vuelve igual a la longitud de la array de caracteres:
    • Compruebe si la array de caracteres es una string de paréntesis equilibrada
    • Si la condición anterior es verdadera, imprima la string
  • Si el carácter actual ch[index] es ‘(‘ o ‘)’ , realice una llamada recursiva en el siguiente índice
  • Si el carácter actual ch[index] es ‘?’ después:
    • Reemplácelo con ‘(‘ y realice una llamada recursiva en el siguiente índice
    • Reemplácelo con ‘)’ y realice una llamada recursiva en el siguiente índice
    • Cámbielo de nuevo a ‘?’ antes de volver de la función

A continuación se muestra la implementación del enfoque anterior:

// 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 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);
    }
}

# 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# 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

<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>

(())
()()

Complejidad de tiempo: O(N*2^N)
Espacio auxiliar: O(N)