问题描述

给定一个字符串S，只包含(，)和小写字母，这个字符串满足以下条件：

• 删除所有小写字母后，将剩余的括号顺次连接成一个括号序列，这个括号序列是一个合法的括号序列(所有的左右括号两两匹配)

字符串中每一类小写字母对应一个小球。此外，我们有一个箱子。 一个人按照1,2,3,...,|S|的顺序取球：

• 如果Si为(，什么也不做。
• 如果Si为小写字母，就将这个字母对应的小球放入箱子中。如果这个小球已经出现在箱子中，他会晕倒。
• 如果Si为)，找到和这个右括号匹配的左括号，记其下标为j，将j到i操作中放入的小球全部取出。 在这个过程中，如果他晕倒了，输出No。否则输出Yes。

样例

输入样例#1

• ((a)ba)

输出样例#1

• Yes

输入样例#2

• (a(ba))

输出样例#2

• No

输入样例#3

• (((())))

输出样例#3

• Yes

输入样例#4

• abca

输出样例#4

• No

我的思路

不可以，总司令55分 暴力，直接for循环，当然结果就是TLE——9分。

我的代码

//不可以，总司令版本
#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"No";
    return 0;
}

//暴力版本
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M=3e5+5;
string s;
char box[M];
signed main(){
    cin>>s;
    int len=s.size();
    for(int i=0;i<=len;i++){
        if(s[i]=='(')continue;
        if(s[i]==')'){
            for(int j=i;j>=0;j--){
                if(s[j]==i){
                    for(int k=i;k<=j;k++)box[k]=' ';
                }
            }
        }
        else{
            for(int j=0;j<=len;j++){
                if(box[j]==s[i]){
                    cout<<"No";
                    return 0;
                }
            }
        }
    }
    cout<<"Yes";
    return 0;
}