Trace
10.27 每日一题
传送门：https://leetcode-cn.com/problems/remove-invalid-parentheses/
Problem
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
1
2
| 输入：s = "()())()"
输出：["(())()","()()()"]
|
示例 2：
1
2
| 输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
|
示例 3：
提示：
1 <= s.length <= 25s 由小写英文字母以及括号 '(' 和 ')' 组成s 中至多含 20 个括号
方法一：dfs+剪枝
思路
我们发现，删除的无效括号的最小数量是可以提前求出来的。
可以用一个计数器$lnum$来模拟栈，往栈中不断地添加左括号；
之后出现的右括号都可以去栈中匹配左括号，最后栈中剩下的即为要删去的左括号，数量等于$lnum$。
右括号出现时，栈中没有左括号用来匹配，则右括号需要删去，计数器$rnum$++，记录需要删去的右括号数量。
$dfs$搜索
$dfs$所有删去$lnum$个左括号、$rnum$个右括号的序列，并判断是否有效。
剪枝
记录当前序列中的左括号数目$lc$与右括号数目$rc$，如果右括号数目$rc>lc$，则这个序列一定为无效序列，停止搜索。
去重
按照上述算法搜索出的结果中可能含有重复序列，比如当前遇到的字符串为” (((())”，去掉前四个左括号中的任意一个，生成的字符串是一样的，均为 “(())”。
程序
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
81
82
83
84
85
86
| class Solution {
public:
vector<string> ans;
bool isValid(string s){
stack<char> st;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
st.push(s[i]);
}
else if(s[i]==')'){
if(st.empty()){
return false;
}
else{
if(st.top()!='('){
return false;
}
else{
st.pop();
}
}
}
}
return true;
}
void dfs(string s,int lremove,int rremove,int start,int lc,int rc){
if(lremove==0&&rremove==0){
if(isValid(s)){
ans.push_back(s);
}
return;
}
for(int i=start;i<s.size();i++){
if(i!=start && s[i]==s[i-1]){
if(s[i]=='(') lc++;
if(s[i]==')') rc++;
continue;
}
if(lremove>0&&s[i]=='('){
dfs(s.substr(0,i)+s.substr(i+1),lremove-1,rremove,i,lc,rc);
}
if(rremove>0&&s[i]==')'){
dfs(s.substr(0,i)+s.substr(i+1),lremove,rremove-1,i,lc,rc);
}
if(s[i]=='('){
lc++;
}
if(s[i]==')'){
rc++;
}
if(rc>lc){
break;
}
}
}
vector<string> removeInvalidParentheses(string s) {
int lnum=0;
int rnum=0;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
lnum++;
}
else if(s[i]==')'){
if(lnum>0){
lnum--;
}
else{
rnum++;
}
}
}
dfs(s,lnum,rnum,0,0,0);
return ans;
}
};
|
时间复杂度：$O(n*2^n)$，$n$为字符串的长度，长度为$n$的字符串最多有$2^n$个子串，需要对每个子串进行一次合法性判断。
方法二：bfs
思路
注意到题目说的是删去最少的括号，我们可以每次删去一个括号，就所有删去一个括号的操作作为$bfs$的一层，判断这一层有没有符合条件的序列；如果没有就继续删一个括号，转向下一层，以此类推，一旦在某一层找到答案便停止搜索。
我们做$bfs$，上一层$level$和下一层$level$之间的关系为：把所有上一层$level$中的每个元素都拿出来，列举出在删除一个括号后的所有可能的情况。(不管删除以后是否合法），添加到下一个$level$中的元素。
例如：$current level$是 ["(()", "())"]
1
2
3
4
| - 那么下一层level中的元素应该是:
1. 对 "(()" 删除一个括号的所有可能为： (), (), ((
2. 对 "())" 删除一个括号的所有可能为： (), )), ()
|
注意到有重复的序列，可以使用$unordered_set$代替$queue$，以达到去重的目的。
程序
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
| class Solution {
public:
bool isvalid(string s){
int ans=0;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
ans++;
}
else if(s[i]==')'){
ans--;
if(ans<0){
return false;
}
}
}
if(ans>0) return false;
return true;
}
vector<string> removeInvalidParentheses(string s) {
unordered_set<string> q;
vector<string> ans;
q.insert(s);
while(!q.empty()){
for(auto ss:q){
if(isvalid(ss)){
ans.push_back(ss);
}
}
if(ans.size()){
return ans;
}
unordered_set<string> curq;
for(auto ss:q){
for(int i=0;i<ss.size();i++){
if(i>0&&ss[i]==ss[i-1]){
continue;
}
if(ss[i]=='('||ss[i]==')'){
curq.insert(ss.substr(0,i)+ss.substr(i+1));
}
}
}
q=curq;
}
return ans;
}
};
|
时间复杂度：$O(n*2^n)$，$n$为字符串的长度，长度为$n$的字符串最多有$2^n$个子串，需要对每个子串进行一次合法性判断。
