题解 | #括号匹配#

分类：①自身匹配的字符串，个数为self，匹配对数为self*self

②（去掉自身可匹配的（）后）只剩左括号和只剩右括号的可匹配为另一类，

匹配顺序唯一，左括号再前，右括号在后

题目描述不太好理解，其实就是暴力法：从头遍历2遍，只要能匹配就算一对 但是问题在于时间复杂度太大，遂另寻它法

借鉴前人思路，看到用化简的思路，直接用string的find和erase，很妙

下面仍是用栈写的

便于理解版

#include<iostream>
#include<string>
#include<stack>
#include<cstring>
using namespace std;

stack<int>kuo;//括号栈
string ss;
int Left[300000],Right[300000];//只剩左括号、右括号的数组，记录化简后括号个数
int l_index=0,r_index=0;//数组长度
bool match(string s){//匹配函数，若本身匹配返回真；否则计算化简后括号个数
    bool flag=true;
    int left=0,right=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='(')kuo.push(i);
        else if(!kuo.empty())kuo.pop();
        else {  //栈内无左括号来配对
            right++;//剩余右括号++
            flag=false;
        };
    }
    if(!kuo.empty()){
        while(!kuo.empty()){//栈内有多余左括号
            left++;//剩余左括号++
            kuo.pop();
        }
        
        flag=false;
    }
    if(left==0&&right!=0)Right[r_index++]=right;//只剩右括号的
    else if(left!=0&&right==0)Left[l_index++]=left;//只剩左括号的
                                                  //左右括号都剩)(，不可能匹配
    return flag;
}

int main(){
    int n,self=0,answer=0;
    
    memset(Left,0,sizeof(Left));
    memset(Right,0,sizeof(Right));
    scanf("%d",&n);
    int k=0;
    for(int i=0;i<n;i++){
        cin>>ss;
        if(match(ss))self++;
       
    }
    answer=answer+self*self;
    for(int i=0;i<l_index;i++){
            for(int j=0;j<r_index;j++){
               if(Left[i]==Right[j]){//遍历左右括号数组，个数相同即配对
                 answer++;
               }
            }
    }
    
    printf("%d",answer);
    
    return 0;
}

空间优化版

#include<iostream>
#include<string>
#include<stack>
#include<cstring>
using namespace std;

stack<int>kuo;
string ss;
int signal[300000];//记录左右括号个数差
int indexx=0;
bool match(string s){
    bool flag=true;
    int left=0,right=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='(')kuo.push(i);
        else if(!kuo.empty())kuo.pop();
        else {
            right++;
            flag=false;
        };
    }
    if(!kuo.empty()){
        while(!kuo.empty()){
            left++;
            kuo.pop();
        }
        
        flag=false;
    }
    if((left==0&&right!=0)||(left!=0&&right==0))signal[indexx++]=left-right;
    //只记录满足条件的括号个数差
 
    return flag;
}

int main(){
    int n,self=0,answer=0;
    
    memset(signal,0,sizeof(signal));

    scanf("%d",&n);
    int k=0;
    for(int i=0;i<n;i++){
        cin>>ss;
        if(match(ss))self++;
       
    }
    answer=answer+self*self;
    for(int i=0;i<indexx;i++){
            for(int j=i+1;j<indexx;j++){//无需从头开始，因为配对顺序唯一，（在前、）在后
               if(signal[i]+signal[j]==0){
                 answer++;
               }
            }
    }

    printf("%d",answer);
    
    return 0;
}