参考文献
合法括号序列的判断条件:
1.左右括号数量相同
2.任意一个前缀中,左括号数量 >= 右括号数量
C++ 代码
class Solution {
public:
// 计算需要删除的左括号数量l,需要删除的右括号数量r
// 利用上述结论提前剪枝
// 以及需要避免重复,即 ((( 这几个左括号删除一个结果都一样,因此需要枚举删除的数量
vector<string> res;
vector<string> removeInvalidParentheses(string s) {
int l = 0, r = 0;
for(char c : s){
if(c == '(')l++;
if(l==0 && c == ')')r++;
else if(c == ')')l--;
}
// cout << l << "," << r << endl;
dfs(s, 0, "", 0, l, r);
return res;
}
// s:原字符串,u:当前搜索到的字符串下标,path:当前的结果字符串
// cnt: 左括号减右括号的值;l:剩余左括号的数量;r:剩余右括号的数量
void dfs(string s, int u, string path, int cnt, int l, int r){
if(u == s.size()){
if(!cnt){
res.push_back(path);
}
return;
}
if(s[u]!='(' && s[u]!=')')dfs(s, u+1, path+s[u], cnt, l, r);
else if(s[u] == '('){
// 计算连续的(数量,然后枚举删除几个
int k = u;
while(k<s.size() && s[k]=='(')k++;
l -= k-u; // 先假设一次性删除完连续的左括号
for(int i=k-u; i>=0; i--){
if(l>=0)dfs(s, k, path, cnt, l, r);
// 每次再补回来一个 (
l++, cnt++;
path += '(';
}
} else if(s[u] == ')'){
int k = u;
while(k<s.size() && s[k]==')')k++;
r -= k-u;
// 每次再补回来一个 )
for(int i=k-u; i>=0; i--){
// 需要满足 左括号数量大于右括号,且还可以删除右括号
if(cnt >=0 && r>=0)dfs(s, k, path, cnt, l, r);
r++, cnt--;
path += ')';
}
}
}
};