Gibt alle ausgeglichenen Klammerzeichenfolgen aus, die durch Ersetzen des Platzhalterzeichens „?“ gebildet werden.

Ausgewogene Klammern bedeuten, dass, wenn wir eine Klammerfolge haben, jede offene Klammer eine entsprechende schließende Klammer hat und die Klammerpaare korrekt verschachtelt sind. Die Größe der Zeichenfolge sollte eine gerade Zahl sein. In diesem Problem erhalten wir eine Klammerzeichenfolge, die das Zeichen „?“ enthält, und unsere Aufgabe besteht darin, jede mögliche ausgeglichene Klammerzeichenfolge zu bilden, indem wir „?“ durch die entsprechende Klammer ersetzen. In unserer angegebenen Zeichenfolge werden nur Klammern „(“ und „)“ verwendet.

Beispiel Beispiel

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

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Durch Ersetzen von „?“ kann nur eine ausgeglichene Zeichenfolge gebildet werden.

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

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

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Es gibt zwei Möglichkeiten, eine ausgewogene Saite zu bilden.

• Eine Möglichkeit besteht darin, die Indizes 0, 1 und 2 durch eine offene Klammer und die anderen Indizes durch eine geschlossene Klammer zu ersetzen.

• Die zweite Methode besteht darin, die Indizes 0, 1 und 3 durch eine offene Klammer und die anderen Indizes durch eine geschlossene Klammer zu ersetzen.

• Die dritte Methode besteht darin, die Indizes 0, 1 und 4 durch offene Klammern und die anderen Indizes durch geschlossene Klammern zu ersetzen.

• Die vierte Methode besteht darin, die Positionen an Index 0, 2 und 3 durch eine offene Klammer und die anderen Indexpositionen durch eine geschlossene Klammer zu ersetzen.

• Die letzte Möglichkeit besteht darin, die Indizes 0, 2 und 4 durch offene Klammern und die anderen Indizes durch geschlossene Klammern zu ersetzen.

Methode

Wir haben das Beispiel der angegebenen Zeichenfolge oben gesehen, fahren wir mit dem nächsten Schritt fort –

Wir können die Backtracking-Methode verwenden, um dieses Problem zu lösen.

Lassen Sie uns diese Methode unten besprechen -

• Zunächst initialisieren wir eine Funktion namens „create“, um alle möglichen Zeichenfolgen zu erstellen, nachdem „?“ durch Klammern ersetzt wurde, mit den Parametern str und index = 0.

• In dieser Funktion,

−> Zunächst legen wir die Rahmenbedingungen fest. Wenn wir das Ende der Zeichenfolge erreichen, müssen wir die Zeichenfolge an die Funktion „check“ übergeben, um zu überprüfen, ob die Zeichenfolge ausgeglichen ist. Wenn es ausgeglichen ist, drucken Sie die Zeichenfolge aus.

−>Wenn das aktuelle Zeichen der Zeichenfolge „?“ ist,

Ersetzen Sie es zunächst durch eine offene Klammer und rufen Sie dieselbe Funktion auf, um zu prüfen, ob das Ende der Zeichenfolge erreicht ist.

Zweitens ersetzen Sie es durch die schließende Klammer und rufen Sie dieselbe Funktion erneut auf, um zu überprüfen, ob wir das Ende der Zeichenfolge erreicht haben.

Abschließend verfolgen wir die Zeichenfolge zurück und weisen das aktuelle Zeichen „?“ zu.

−> Andernfalls, wenn das aktuelle Zeichen der Zeichenfolge eine Klammer ist, wechseln Sie zum nächsten Index, indem Sie dieselbe Funktion aufrufen.

• Initialisieren Sie die Funktion „Prüfen“, um zu überprüfen, ob die Zeichenfolge ausgeglichen ist.

−> In dieser Funktion initialisieren wir den Stack und prüfen dann

−> Wenn das erste Zeichen der Zeichenfolge eine schließende Klammer ist, geben Sie false zurück

−> Wenn die aktuelle Klammer geschlossen ist, gibt es zwei Situationen: Wenn der Stapel leer ist, wird false zurückgegeben, da keine entsprechende offene Klammer vorhanden ist. Andernfalls entfernen Sie die entsprechende offene Klammer aus dem Stapel.

−> Abschließend prüfen wir, ob der Stapel leer ist, was bedeutet, dass die Zeichenfolge ausgeglichen ist und „true“ zurückgibt. Andernfalls sind noch einige Klammern übrig, was bedeutet, dass die Zeichenfolge unausgeglichen ist und „false“ zurückgibt.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Das Folgende ist der C++-Code, der für die obige Backtracking-Methode verwendet wird, um alle ausgeglichenen Zeichenfolgen zu erhalten

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

Ausgabe

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

Zeitkomplexität und Raumkomplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N*(2^N)), da wir die Zeichenfolge zurückverfolgen müssen.

Die räumliche Komplexität des obigen Codes beträgt O(N), da wir die Klammern auf dem Stapel speichern.

Wobei N die Größe der Zeichenfolge ist.

Fazit

In diesem Tutorial haben wir ein Programm implementiert, das alle ausgeglichenen Klammerzeichenfolgen ausgibt, die durch Ersetzen des Platzhalterzeichens „?“ gebildet werden können. Wir haben eine Backtracking-Methode implementiert. Die zeitliche Komplexität beträgt O(N*(2^N) und die räumliche Komplexität beträgt O(N). Wobei N die Größe der Zeichenfolge ist.

Das obige ist der detaillierte Inhalt vonGibt alle ausgeglichenen Klammerzeichenfolgen aus, die durch Ersetzen des Platzhalterzeichens „?“ gebildet werden.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!