题目描述
找到最小删除个数的合法括号序列的方案
算法1
(爆搜) $O(2^n * n)$
合法括号序列:
1) 序列中,左括号数量 == 右括号数量
2) 任意前缀序列中,左括号数量 >= 右括号数量
剪枝策略1:先预处理出来:最小删除的左括号数量,最小删除的右括号数量
剪枝策略2: 找到一段'(' 计算出这一段的数量,每次搜索删掉的个数,因为删哪个都一样
C++ 代码
class Solution {
public:
vector<string> ans;
vector<string> removeInvalidParentheses(string s) {
// l: 是当前左括号数量 - 右括号数量 r: 需要删除的右括号数量
// 遇到左括号无条件入;
// 遇到右括号:如果当前右括号加进来之后括号序列不合法,则记录此右括号需要删除 r++;
// 如果当前右括号加进来之后括号序列合法,则继续做 l--;
int l = 0, r = 0;
for (auto& c: s)
if (c == '(') l++;
else if (c == ')') {
if (l == 0) r++;
else l--;
}
// 此时l为走到最后了 左括号 - 右括号的数量,已经做完了,所以还多的左括号需要删去(最小左括号)
// 此时r为需要删去的最小右括号
dfs(s, 0, "", 0, l, r);
return ans;
}
// cnt : 当前 左括号数量 - 右括号数量
void dfs(string& s, int u, string path, int cnt, int l, int r) {
if (u == s.size()) {
if (!cnt) ans.push_back(path);
return ;
}
// 如果不是 '(' 或者 ')' 则直接放入path,继续爆搜
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++;
// k - u 为这一段的数量
l -= k - u;
for (int i = k - u; i >= 0; i--) {
// 需要满足剩下还需要删除的左括号数量 l 非负
if (l >= 0) dfs(s, k, path, cnt, l, r);
// 因为i 从k - u 开始枚举,从大到小枚举,每次需要加回来一个'('
path += '(';
cnt++, l++;
}
} 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 -- ) {
// 需要满足剩下还需要删除的左括号数量 l 非负,且 cnt 合法,只有右括号需要判断 cnt,
// 右括号cnt才会--
if (cnt >= 0 && r >= 0) dfs(s, k, path, cnt, l, r);
path += ')';
cnt --, r ++ ;
}
}
}
};