列印所有可以透過替換萬用字元“？”形成的平衡括號字串

---

平衡括號是指，如果我們有一串括號，則每個開括號都有一個對應的閉括號，並且括號對是正確巢狀的。字串的大小應該是偶數。在這個問題中，我們給定了一個也包含字元“？”的括號字串，我們的任務是透過將“？”替換為合適的括號來形成所有可能的平衡括號字串。在給定的字串中，只使用了圓括號“（”和“）”。

示例

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 是字串的大小。