【LetMeFly】301.删除无效的括号：二进制枚举 / 回溯
力扣题目链接：https://leetcode.cn/problems/remove-invalid-parentheses/
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25s 由小写英文字母以及括号 '(' 和 ')' 组成s 中至多含 20 个括号
解题方法一：二进制枚举
首先遍历一遍原始字符串得到括号的下标有哪些、得到至少需要移除多少个括号。
关于至少需要移除多少个字符，可以参考昨天的题目《921.使括号有效的最少添加：一次遍历（贪心）》。
简言之就是使用一个变量left记录左括号比右括号多几个，left < 0则说明需要移除当前右括号；以及最终剩下left个未配对的左括号也需要被移除。
假设括号有m个，那么我们可以使用一个m位的二进制数$i\in [0, 2^m)$来表示保留哪个括号（其中i二进制下第j位为1的话表示整个字符串第j个括号被删除）。
假设要移除k个括号，如果i二进制下恰好有k个1，则构造对应的字符串，并遍历一遍看看该字符串是否合法。
关于一个括号序列字符串是否合法，类似问题“至少需要移除多少个字符使得括号序列合法”，如果至少需要移除0个括号则说明原始字符串合法。
时空复杂度
- 时间复杂度$O(2^m+n\times C_m^k)$
- 空间复杂度$O(n\times C_m^k)$
其中$n=len(s)$，$m$是字符串中的括号数量，$k$是至少需要移除括号的数量。
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
class Solution {
private:
vector<int> idxs;
int mini_remove;
void getInfo(const string& s) {
int left = 0;
mini_remove = 0;
for (int i = 0, n = s.size(); i < n; i++) {
if (s[i] == '(') {
idxs.push_back(i);
left++;
} else if (s[i] == ')') {
idxs.push_back(i);
if (left) {
left--;
} else {
mini_remove++;
}
}
}
mini_remove += left;
}
string genS(const string& s, int mask) {
string this_s;
this_s.reserve(s.size() - mini_remove);
vector<int> deleted;
deleted.reserve(idxs.size());
for (int i = 0; i < idxs.size(); i++) {
if (mask >> i & 1) {
deleted.push_back(idxs[i]);
}
}
for (int is = 0, ic = 0; is < s.size(); is++) {
if (ic < deleted.size() && is == deleted[ic]) {
ic++;
} else {
this_s.push_back(s[is]);
}
}
return this_s;
}
bool ok(const string& s) {
int left = 0;
for (int i = 0, n = s.size(); i < n; i++) {
if (s[i] == '(') {
left++;
} else if (s[i] == ')') {
if (left) {
left--;
} else {
return false;
}
}
}
return !left;
}
public:
vector<string> removeInvalidParentheses(const string& s) {
unordered_set<string> se;
getInfo(s);
int parentheses = idxs.size();
for (int i = 0, to = 1 << parentheses; i < to; i++) {
if (__builtin_popcount(i) != mini_remove) {
continue;
}
string this_s = genS(s, i);
if (ok(this_s)) {
se.insert(this_s);
}
}
return vector<string>(se.begin(), se.end());
}
};
|
解题方法二：回溯
类似方法一，遍历一次原始字符串得到需要移除多少左括号、需要移除多少右括号。
写一个回溯函数dfs(s, idx, left, left_removed, right_removed)，其中：
s是原始字符串idx是当前遍历到的下标left是当前已经保留的左括号比右括号多几个left_removed是当前已经移除的左括号数量right_removed是当前已经移除的右括号数量
如果idx == s.size()，则说明已经遍历完了原始字符串，终止递归。递归终止之前看下如果left为零、left_removed和right_removed分别等于需要移除的左右括号数量，则说明找到了一种可行的移除方案，放入答案集合中。
否则开始回溯尝试：
- 如果当前字符是左括号
(，并且还有左括号可以移除（left_removed < remove_left），则尝试移除当前左括号；
- 如果当前字符是右括号
)，并且还有右括号可以移除（right_removed < remove_right），则尝试移除当前右括号；
- 尝试不移除当前字符（只要不是 “
left==0并且当前字符是右括号”就可以尝试保留当前字符）。递归结束回来记得弹出当前保留的字符。
时空复杂度
- 时间复杂度$O(n \times 2^m)$
- 空间复杂度$O(n\times C_m^k)$
其中$n=len(s)$，$m$是字符串中的括号数量
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
class Solution {
private:
int remove_left, remove_right;
string now;
unordered_set<string> ans;
void getInfo(const string& s) {
remove_left = remove_right = 0;
for (char c : s) {
if (c == '(') {
remove_left++;
} else if (c == ')') {
if (remove_left) {
remove_left--;
} else {
remove_right++;
}
}
}
}
void dfs(const string& s, int idx, int left, int left_removed, int right_removed) {
if (idx == s.size()) {
if (left == 0 && left_removed == remove_left && right_removed == remove_right) {
ans.insert(now);
}
return;
}
if (s[idx] == '(' && left_removed < remove_left) {
dfs(s, idx + 1, left, left_removed + 1, right_removed);
}
if (s[idx] == ')' && right_removed < remove_right) {
dfs(s, idx + 1, left, left_removed, right_removed + 1);
}
left += s[idx] == '(' ? 1 : s[idx] == ')' ? -1 : 0;
if (left < 0) {
return;
}
now.push_back(s[idx]);
dfs(s, idx + 1, left, left_removed, right_removed);
now.pop_back();
}
public:
vector<string> removeInvalidParentheses(const string& s) {
getInfo(s);
now.reserve(s.size() - remove_left - remove_right);
dfs(s, 0, 0, 0, 0);
return vector<string>(ans.begin(), ans.end());
}
};
|
End
今日LeetCode.每日一题连续1906天了。
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源