平衡括號意味著如果我們有一串括號，那麼每個開括號都有一個對應的閉括號，括號對是正確嵌套的。字串的大小應該是偶數。在這個問題中，我們給出了一個包含字元'?'的括號字串，我們的任務是透過將'?'替換為適當的括號來形成每個可能的平衡括號字串。在我們給定的字串中，只使用圓括號'('和')'。
Input 1: str = “()(?)?” Output 1: ()(())
只有一個平衡的字串可以透過替換'?'來形成。
Input 2: str = “??????”
Output 2: ((())) (()()) (())() ()(()) ()()()
有兩種可能的方法來形成一個平衡的字串。
一種方法是用一個開括號取代索引0、1和2，用一個閉括號取代其他索引。
第二種方法是用一個開括號取代索引0、1和3，並用一個閉括號取代其他索引。
第三種方法是用開括號取代索引0、1和4，用閉括號取代其他索引。
第四種方法是用一個開括號替換索引為0、2和3的位置，用一個閉括號取代其他索引的位置。
最後一種方法是用開括號取代索引0、2和4，用閉括號取代其他索引。
我們已經看到了上面給定字串的範例，讓我們繼續下一步的方法-
我們可以用回溯法來解決這個問題。
讓我們在下面討論這個方法 -
首先，我們將初始化一個名為'create'的函數，用於在將'?'替換為括號後創建所有可能的字串，參數為str和index = 0。
在這個函數中，
#−> 首先，我們設定了基本條件。如果我們到達了字串的結束點，那麼我們必須將該字串傳遞給「check」函數來驗證字串是否平衡。如果它是平衡的，則列印該字串。
−>如果字串的目前字元是‘?’，
首先，將其替換為開括號，並呼叫相同的函數來檢查是否到達字串的末端。
其次，用閉括號替換它，並再次呼叫相同的函數來檢查我們是否已經到達字串的末尾。
最後，我們回溯字串並將目前字元賦值為‘?’
−> 否則，如果字串的當前字元是括號，則透過呼叫相同的函數移動到下一個索引。
初始化'check'函數以驗證字串是否平衡。
−> 在這個函數中，我們初始化堆疊，然後進行檢查
−> 如果字串的第一個字元是閉括號，則傳回false
−> 如果目前括號已關閉，則有兩種情況：如果堆疊為空，則傳回false，因為沒有對應的開括號。否則，從棧中彈出對應的開括號。
−> 最後，我們檢查堆疊是否為空，如果為空則表示字串是平衡的，回傳true，否則還有一些括號剩餘，表示字串不平衡，回傳false。
下面是用於上述回溯方法取得所有平衡字串的C 程式碼
#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;
}
((())) (()()) (())() ()(()) ()()()
時間複雜度與空間複雜度
上述程式碼的時間複雜度為O(N*(2^N))，因為我們需要在字串上進行回溯。
上述程式碼的空間複雜度為O(N)，因為我們將括號儲存在堆疊中。
其中N是字串的大小。
在本教程中，我們實作了一個程序，用於列印所有平衡的括號字串，可以透過替換通配符‘?’來形成。我們實作了一種回溯的方法。時間複雜度為O(N*(2^N)，空間複雜度為O(N)。其中N為字串的大小。
以上是列印所有透過替換通配符「？」而形成的平衡括號字串的詳細內容。更多資訊請關注PHP中文網其他相關文章！
