可拼接成正则括号序列的最大括号序列对数

---

正则括号序列是指包含开闭两种类型括号且括号正确闭合的字符串。给定的序列可能是正确对称的，也可能不是。在这个问题中，我们得到一个包含括号序列的字符串列表，我们必须找到可以连接成单个正则括号序列的对数。

示例

输入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)。