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.
Input 1: str = “()(?)?” Output 1: ()(())
Durch Ersetzen von „?“ kann nur eine ausgeglichene Zeichenfolge gebildet werden.
Input 2: str = “??????”
Output 2: ((())) (()()) (())() ()(()) ()()()
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.
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.
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;
}
((())) (()()) (())() ()(()) ()()()
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.
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!
