mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
131 lines
4.8 KiB
Markdown
131 lines
4.8 KiB
Markdown
# [301. Remove Invalid Parentheses](https://leetcode.com/problems/remove-invalid-parentheses/)
|
||
|
||
# 思路
|
||
|
||
## 思路一、暴力BFS
|
||
|
||
由于要求去掉最少的字符，所以考虑用BFS（不能DFS）：把给定字符串入队，然后取出检测其是否合法，若合法就将其存放到结果数组res；不合法的话，对其进行遍历，依次穷举去掉每个括号然后得到一个新串，如果这个字符串之前没有遇到过（所以需要用一个set来记录出现过的字符串），将其入队。
|
||
|
||
注意：一旦res不为空，就说明上一轮循环已经找到了合法的串，再进行循环的话会继续去掉更多括号，所以没必要继续循环。
|
||
|
||
本方法存在大量重复计算，所以比较耗时。
|
||
|
||
|
||
## 思路二、DFS
|
||
注意到要求去掉最少的字符，所以返回的所有字符串的长度都是固定的（而且分别删除多少左右括号也是固定的）。而且我们可以提前把这个长度算出来，这样就可以使用DFS了。
|
||
|
||
为此，我们首先先统计多余的括号的数量，用left表示多余的左括号，right表示多余的右括号，一次遍历就可算出left和right，例
|
||
```
|
||
0 1 2 3 4 5 6 7
|
||
( ) ) ) ( ( ( )
|
||
|
||
i = 0, left = 1, right = 0
|
||
i = 1, left = 0, right = 0
|
||
i = 2, left = 0, right = 1
|
||
i = 3, left = 0, right = 2
|
||
i = 4, left = 1, right = 2
|
||
i = 5, left = 2, right = 2
|
||
i = 6, left = 3, right = 2
|
||
i = 7, left = 2, right = 2
|
||
```
|
||
上例有两个多余的左括号，两个多余的右括号。
|
||
|
||
然后我们就可以使用DFS：
|
||
* 当`left == 0 && right == 0`时，判断是否合法，若合法则存入结果数组res中；
|
||
* 否则，需要进行递归。遍历当前字符串，如果当前字符为左括号且`left > 0`，那么表示可以删掉这个左括号，然后递归调用；右括号同理。
|
||
|
||
注意为了避免重复计算，我们用变量start表示当前递归开始的位置，遍历时只需从start开始就可以了而不需要每次都从头开始。而且，对于相邻的相同括号，只需要删除第一个，比如 "())"，这里有两个右括号，不管删第一个还是删第二个右括号都会得到 "()"，没有区别，所以只用算一次就行了。
|
||
|
||
相比于思路一，本思路避免了很多重复计算，因此高效很多。
|
||
|
||
# C++
|
||
|
||
## 思路一
|
||
``` C++
|
||
class Solution {
|
||
private:
|
||
bool valid(const string &s){ // 判断字符串是否合法
|
||
int cnt = 0;
|
||
for(int i = 0; i < s.size(); i++){
|
||
if(s[i] == '(') cnt++;
|
||
else if(s[i] == ')' && (--cnt < 0)) return false;
|
||
}
|
||
return cnt == 0;
|
||
}
|
||
|
||
public:
|
||
vector<string> removeInvalidParentheses(string s) {
|
||
vector<string>res;
|
||
queue<string>q; q.push(s);
|
||
unordered_set<string>visited; visited.insert(s);
|
||
|
||
while(!q.empty()){
|
||
string ss = q.front(); q.pop();
|
||
if(valid(ss)) res.push_back(ss);
|
||
else{
|
||
if(!res.empty()) continue; // 在上一轮已经找到了最长的合法串, 接下来的肯定要短些
|
||
// 穷举:删除每个括号
|
||
for(int i = 0; i < ss.size(); i++){
|
||
if(ss[i] != '(' && ss[i] != ')') continue;
|
||
if(i > 0 && ss[i] == ss[i-1]) continue;
|
||
string subs = ss.substr(0, i) + ss.substr(i+1);
|
||
if(visited.find(subs) == visited.end()) {
|
||
q.push(subs);
|
||
visited.insert(subs);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
return res;
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路二
|
||
|
||
``` C++
|
||
class Solution {
|
||
private:
|
||
bool valid(const string &s){
|
||
int cnt = 0;
|
||
for(int i = 0; i < s.size(); i++){
|
||
if(s[i] == '(') cnt++;
|
||
else if(s[i] == ')' && (--cnt < 0)) return false;
|
||
}
|
||
return cnt == 0;
|
||
}
|
||
|
||
void DFS(string s, int left, int right, int start, vector<string> &res){
|
||
if(!left && !right){
|
||
if(valid(s)) res.push_back(s);
|
||
return;
|
||
}
|
||
for(int i = start; i < s.size(); i++){
|
||
if(i > start && s[i] == s[i-1]) continue; // 去重
|
||
|
||
if(left > 0 && s[i] == '(')
|
||
DFS(s.substr(0, i) + s.substr(i+1), left-1, right, i, res);
|
||
else if(right > 0 && s[i] == ')')
|
||
DFS(s.substr(0, i) + s.substr(i+1), left, right-1, i, res);
|
||
}
|
||
}
|
||
|
||
public:
|
||
vector<string> removeInvalidParentheses(string s) {
|
||
vector<string> res;
|
||
|
||
int left = 0, right = 0;
|
||
for(int i = 0; i < s.size(); i++){
|
||
if(s[i] == '(') left++;
|
||
else if(s[i] == ')'){
|
||
if(left > 0) left--;
|
||
else right++;
|
||
}
|
||
}
|
||
|
||
DFS(s, left, right, 0, res);
|
||
return res;
|
||
}
|
||
};
|
||
``` |