Maison >développement back-end >C++ >Imprime toutes les chaînes de parenthèses équilibrées formées en remplaçant le caractère générique '?'
Parenthèses équilibrées signifie que si nous avons une chaîne de parenthèses, alors chaque parenthèse ouverte a une parenthèse fermante correspondante et les paires de parenthèses sont correctement imbriquées. La taille de la chaîne doit être un nombre pair. Dans ce problème, nous recevons une chaîne de crochets contenant le caractère « ? » et notre tâche est de former toutes les chaînes de crochets équilibrées possibles en remplaçant « ? » par le crochet approprié. Dans notre chaîne donnée, seules les parenthèses '(' et ')' sont utilisées.
Input 1: str = “()(?)?” Output 1: ()(())La traduction chinoise de
Seule une chaîne équilibrée peut être formée en remplaçant '?'.
Input 2: str = “??????”
Output 2: ((())) (()()) (())() ()(()) ()()()La traduction chinoise de
Il existe deux manières possibles de former une corde équilibrée.
Une solution consiste à remplacer les indices 0, 1 et 2 par une parenthèse ouverte et les autres indices par une parenthèse fermée.
La deuxième méthode consiste à remplacer les indices 0, 1 et 3 par une parenthèse ouverte et les autres indices par une parenthèse fermée.
La troisième méthode consiste à remplacer les indices 0, 1 et 4 par des parenthèses ouvertes et les autres indices par des parenthèses fermées.
La quatrième méthode consiste à remplacer les positions à l'index 0, 2 et 3 par une parenthèse ouverte et les autres positions de l'index par une parenthèse fermée.
La dernière façon est de remplacer les indices 0, 2 et 4 par des parenthèses ouvertes et les autres indices par des parenthèses fermées.
Nous avons vu l'exemple de la chaîne donnée ci-dessus, passons à l'étape suivante -
Nous pouvons utiliser la méthode du backtracking pour résoudre ce problème.
Parlons de cette méthode ci-dessous -
Tout d'abord, nous allons initialiser une fonction appelée 'create' pour créer toutes les chaînes possibles après avoir remplacé '?' par des crochets, avec les paramètres str et index = 0.
Dans cette fonction,
−> Tout d’abord, nous définissons les conditions de base. Si nous atteignons la fin de la chaîne, alors nous devons passer la chaîne à la fonction "check" pour vérifier que la chaîne est équilibrée. S'il est équilibré, imprimez la chaîne.
−>Si le caractère actuel de la chaîne est « ? »,
Tout d'abord, remplacez-le par un crochet ouvert et appelez la même fonction pour vérifier si la fin de la chaîne est atteinte.
Deuxièmement, remplacez-le par le crochet fermant et appelez à nouveau la même fonction pour vérifier si nous avons atteint la fin de la chaîne.
Enfin, nous revenons en arrière sur la chaîne et attribuons le caractère actuel à « ? »
−> Sinon, si le caractère actuel de la chaîne est un crochet, passez à l'index suivant en appelant la même fonction.
Initialisez la fonction 'check' pour vérifier si la chaîne est équilibrée.
−> Dans cette fonction, nous initialisons la pile puis vérifions
−> Si le premier caractère de la chaîne est un crochet fermant, renvoie false
−> Si la parenthèse actuelle est fermée, il existe deux situations : si la pile est vide, false est renvoyé car il n'y a pas de parenthèse ouverte correspondante. Sinon, retirez le support ouvert correspondant de la pile.
−> Enfin, nous vérifions si la pile est vide. Si elle est vide, cela signifie que la chaîne est équilibrée et renvoie vrai. Sinon, il reste quelques crochets, ce qui signifie que la chaîne est déséquilibrée et renvoie faux.
Ce qui suit est le code C++ utilisé pour la méthode de retour en arrière ci-dessus afin d'obtenir toutes les chaînes équilibrées
#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; }
((())) (()()) (())() ()(()) ()()()
Complexité temporelle et complexité spatiale
La complexité temporelle du code ci-dessus est O(N*(2^N)) car nous devons revenir en arrière sur la chaîne.
La complexité spatiale du code ci-dessus est O(N) car nous stockons les crochets sur la pile.
Où N est la taille de la chaîne.
Dans ce didacticiel, nous avons implémenté un programme qui imprime toutes les chaînes de parenthèses équilibrées pouvant être formées en remplaçant le caractère générique « ? ». Nous avons mis en place une méthode de backtracking. La complexité temporelle est O(N*(2^N) et la complexité spatiale est O(N). Où N est la taille de la chaîne.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!