問題
https://community.topcoder.com/stat?c=problem_statement&pm=14059&rd=16550
解き方
文字列長がnのとき、条件を満たすLCSは必ずn-1となる。
そのようなサブ文字列を全て求めて条件を満たすか確かめれば良い。
サブ文字列の作り方でミスをしてしまった。。
コード
class Bracket107 {
public:
int yetanother(string s) {
int n=s.size();
set<string> ans;
FORE(i,0,n){
string str=s.substr(0,i)+s.substr(i+1,n);
FORE(j,0,n){
string cur=str.substr(0,j)+s[i]+ str.substr(j);
if(s==cur)continue;
int valid=1;
int cnt=0;
FORE(k,0,n){
if(cur[k]=='(')cnt++;
else cnt--;
if(cnt<0)valid=0;
}
if(valid)ans.insert(cur);
}
}
return ans.size();
}
};
public:
int yetanother(string s) {
int n=s.size();
set<string> ans;
FORE(i,0,n){
string str=s.substr(0,i)+s.substr(i+1,n);
FORE(j,0,n){
string cur=str.substr(0,j)+s[i]+ str.substr(j);
if(s==cur)continue;
int valid=1;
int cnt=0;
FORE(k,0,n){
if(cur[k]=='(')cnt++;
else cnt--;
if(cnt<0)valid=0;
}
if(valid)ans.insert(cur);
}
}
return ans.size();
}
};