首頁  >  文章  >  後端開發  >  列印所有透過替換通配符「?」而形成的平衡括號字串

列印所有透過替換通配符「?」而形成的平衡括號字串

PHPz
PHPz轉載
2023-09-08 15:25:02855瀏覽

列印所有透過替換通配符「?」而形成的平衡括號字串

平衡括號意味著如果我們有一串括號,那麼每個開括號都有一個對應的閉括號,括號對是正確嵌套的。字串的大小應該是偶數。在這個問題中,我們給出了一個包含字元'?'的括號字串,我們的任務是透過將'?'替換為適當的括號來形成每個可能的平衡括號字串。在我們給定的字串中,只使用圓括號'('和')'。

範例範例

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

Explanation

的中文翻譯為:

解釋

只有一個平衡的字串可以透過替換'?'來形成。

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

Explanation

的中文翻譯為:

解釋

有兩種可能的方法來形成一個平衡的字串。

  • 一種方法是用一個開括號取代索引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。

Example

的中文翻譯為:

範例

下面是用於上述回溯方法取得所有平衡字串的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中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除