可拼接成正則括號序列的最大括號序列對數

---

正則括號序列是指包含開閉兩種型別括號且括號正確閉合的字串。給定的序列可能是正確對稱的，也可能不是。在這個問題中，我們得到一個包含括號序列的字串列表，我們必須找到可以連線成單個正則括號序列的對數。

示例

輸入1

string arr[] = {“)()”, “()(“, “()()”, “(())”}

輸出：2

解釋 − 對於第一個和第二個字串，我們可以將第一個字串連線到第二個字串之後，得到正則括號序列。第三個和第四個字串已經是正則表示式，因此我們可以輕鬆地將它們新增到一起或連線它們以獲得另一個正則表示式。

輸入2

string arr[] = {“()(“, “()(“}

輸出：0

解釋 − 只有兩種方法可以新增字串，兩者都會產生最終不是正則字串的字串。

樸素方法

在這種方法中，我們將考慮所有對並找到當前字串的最佳匹配。我們將使用巢狀for迴圈遍歷字串，並找到可以構成正則表示式的對。如果我們找到任何對，我們將標記它們為已使用，以免以後再次使用。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check if the string can make a regular expression 
bool matched(string str1, string str2){
   int n = str1.length(); // getting length of the string 
   int m = str2.length();    
   // first putting the first string in front 
   int k = 0;    
   for(int i=0;i<n;i++){
      if(str1[i] == ')'){
         k--;
      }
      else{
         k++;
      }
      if(k < 0){
         break;
      }
   }
   if(k >= 0){
      for(int i=0;i<m;i++){
         if(str2[i] == '('){
            k++;
         }
         else{
            k--;
         }
         if(k < 0){
            return false;
         }
      }
      if(k == 0){
         return true;
      }
   }    
   // updating the value of k to again check by putting second string after first
   k = 0;
   for(int i=0;i<m;i++){
      if(str2[i] == ')'){
         k--;
      }
      else{
         k++;
      }
      if(k < 0){
         return false;
      }
   }
   for(int i=0;i<n;i++){
      if(str1[i] == '('){
         k++;
      }
      else{
         k--;
      }
      if(k < 0){
         return false;
      }
   }
   if(k == 0){
      return true;
   }
   return false;
}
int findRes(string arr[], int n){
   vector<int>used(n); // vector to mark the already used string 
   int ans = 0;    
   // traversing over the array of string 
   for(int i=0; i<n; i++){
      if(used[i] == 1){
         continue; // current string is already concatenated
      }        
      // for the current string finding the best match 
      for(int j=i+1; j < n; j++){
         if(used[j] == 1){
            continue; // current string is already used
         }
         // check if the current string can be matched with this string 
         if(matched(arr[i],arr[j])){
            used[j] = 1;
            ans++;
            break;
         }
      }
   }
   return ans;
}
int main(){
   // given string array;
   string arr[] = {")()", "()(", "()()", "(())"};
   int n = 4; // size of the given string array;    
   // calling the function 
   cout<<"The maximum number of strings that we can concatenate is "<<findRes(arr,n)<<endl;
   return 0;
}

輸出

The maximum number of strings that we can concatenate is 2

時間和空間複雜度

上述程式碼的時間複雜度為O(N*N*L)，其中N是字串的數量，L是字串的長度。

上述程式碼的空間複雜度為O(N)，因為我們使用陣列來儲存已使用字串的索引。

高效方法

在這種方法中，我們將找到當前字串所需的左括號和右括號的數量。如果需要左右括號，則無法使用，否則可以將其與需要相反括號的字串配對。讓我們看看程式碼 -

示例

#include <bits/stdc++.h>
using namespace std;
// function to find the number of string can concatenate
int findRes(string arr[], int n){
   // vector to store the left and rigth parenthesis required
   vector<int>left(100), right(100);    
   // variable to count the number of strings that are already regular expressions 
   int reg = 0;
   int ans = 0; // varaible to store the answer     
   // traversing over the strings  
   for(int i=0; i<n; i++){
      // getting the required number of parenthesis on any side 
      int onLeft = 0, onRight = 0;
      for(int j=0; j<arr[i].length(); j++){
         if(arr[i][j] == '('){
            onRight++;
         }
         else{
            onRight--;
         }
         if(onRight < 0){
            onLeft++;
            onRight = 0;
         }
      }
      if(onLeft == 0 && onRight == 0){
         if(reg == 0){
            reg++;
         }
         else{
            reg = 0;
            ans++;
         }
      }
      else if(onLeft == 0){
         if(left[onRight] == 0){
            right[onRight]++;
         }
         else{
            left[onRight]--;
            ans++;
         }
      }
      else if(onRight == 0){
         if(right[onLeft] == 0){
            left[onLeft]++;
         }
         else{
            right[onLeft]--;
            ans++;
         }
      }
   }
   return ans;
}
// main function 
int main(){
   // given string array;
   string arr[] = {")()", "()(", "()()", "(())"};
   int n = 4; // size of the given string array;    
   // calling the function 
   cout<<"The maximum number of strings that we can concatenate is "<<findRes(arr,n)<<endl;
   return 0;
}

輸出

The maximum number of strings that we can concatenate is 2

時間和空間複雜度

上述程式碼的時間複雜度為O(L*N)，其中L是字串的長度，N是字串的數量。

上述程式碼的空間複雜度為O(L)。

結論

在本教程中，我們學習瞭如何從給定的字串集中找到可以連線起來構成正則表示式的字串數量。我們實現了兩個程式碼，一個時間複雜度為O(L*N*N)，另一個使用額外空間，採用高效方法，時間複雜度為O(L*N)。