Cetak semua rentetan kurungan seimbang yang terbentuk dengan menggantikan aksara kad bebas '?'

Kurungan seimbang bermakna jika kita mempunyai rentetan kurungan, maka setiap kurungan terbuka mempunyai kurungan penutup yang sepadan, dan pasangan kurungan bersarang dengan betul. Saiz rentetan hendaklah nombor genap. Dalam masalah ini, kami diberi rentetan kurungan yang mengandungi aksara '?' dan tugas kami adalah untuk membentuk setiap rentetan kurungan seimbang yang mungkin dengan menggantikan '?' dengan kurungan yang sesuai. Dalam rentetan kami yang diberikan, hanya kurungan '(' dan ')' digunakan.

CONTOHCONTOH

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

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Explain

Hanya rentetan seimbang boleh dibentuk dengan menggantikan '?'.

Input 2: str = “??????”

Output 2: ((()))
(()())
(())()
()(())
()()()

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Explain

Terdapat dua cara yang mungkin untuk membentuk rentetan yang seimbang.

• Salah satu cara ialah menggantikan indeks 0, 1 dan 2 dengan kurungan terbuka dan indeks lain dengan kurungan tertutup.

• Kaedah kedua ialah menggantikan indeks 0, 1, dan 3 dengan kurungan terbuka, dan indeks lain dengan kurungan tertutup.

• Kaedah ketiga ialah menggantikan indeks 0, 1 dan 4 dengan kurungan terbuka dan indeks lain dengan kurungan tertutup.

• Kaedah keempat ialah menggantikan kedudukan pada indeks 0, 2 dan 3 dengan pendakap terbuka dan menggantikan kedudukan indeks yang lain dengan pendakap tertutup.

• Cara terakhir ialah menggantikan indeks 0, 2 dan 4 dengan kurungan terbuka dan indeks lain dengan kurungan tertutup.

kaedah

Kita telah melihat contoh rentetan yang diberikan di atas, mari kita teruskan ke langkah seterusnya -

Kita boleh menggunakan kaedah backtracking untuk menyelesaikan masalah ini.

Mari bincangkan kaedah ini di bawah -

• Pertama, kami akan memulakan fungsi yang dipanggil 'buat' untuk mencipta semua rentetan yang mungkin selepas menggantikan '?' dengan kurungan, dengan parameter str dan indeks = 0.

• Dalam fungsi ini,

−> Mula-mula, kita tetapkan syarat asas. Jika kita mencapai penghujung rentetan, maka kita mesti menghantar rentetan ke fungsi "semak" untuk mengesahkan bahawa rentetan itu seimbang. Jika ia seimbang, cetak rentetan.

−>Jika aksara semasa rentetan ialah ‘?’,

Pertama, gantikannya dengan kurungan terbuka dan panggil fungsi yang sama untuk memeriksa sama ada hujung rentetan tercapai.

Kedua, gantikannya dengan kurungan penutup dan panggil fungsi yang sama sekali lagi untuk memeriksa sama ada kita telah mencapai penghujung rentetan.

Akhir sekali, kami menjejaki rentetan dan menetapkan aksara semasa kepada ‘?’

−> Jika tidak, jika aksara semasa rentetan ialah kurungan, beralih ke indeks seterusnya dengan memanggil fungsi yang sama.

• Mulakan fungsi 'semak' untuk mengesahkan bahawa rentetan itu seimbang.

−> Dalam fungsi ini, kami memulakan tindanan dan kemudian menyemak

−> Jika aksara pertama rentetan ialah kurungan penutup, kembalikan palsu

−> Jika kurungan semasa ditutup, terdapat dua situasi: jika tindanan kosong, palsu dikembalikan kerana tiada kurungan terbuka yang sepadan. Jika tidak, keluarkan kurungan terbuka yang sepadan daripada timbunan.

−> Akhir sekali, kami menyemak sama ada tindanan itu kosong, ini bermakna rentetan itu seimbang dan kembali benar.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Berikut ialah kod C++ yang digunakan untuk kaedah backtracking di atas untuk mendapatkan semua rentetan seimbang

#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;
}

Output

((()))
(()())
(())()
()(())
()()()

Kerumitan masa dan kerumitan ruang

Kerumitan masa kod di atas ialah O(N*(2^N)) kerana kita perlu mengundur rentetan.

Kerumitan ruang kod di atas ialah O(N) kerana kami menyimpan kurungan pada tindanan.

Di mana N ialah saiz rentetan.

KESIMPULAN

Dalam tutorial ini, kami melaksanakan program yang mencetak semua rentetan kurungan seimbang yang boleh dibentuk dengan menggantikan aksara kad bebas ‘?’. Kami melaksanakan kaedah menjejak ke belakang. Kerumitan masa ialah O(N*(2^N), dan kerumitan ruang ialah O(N). Di mana N ialah saiz rentetan.

Atas ialah kandungan terperinci Cetak semua rentetan kurungan seimbang yang terbentuk dengan menggantikan aksara kad bebas '?'. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!