题目描述
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Example1:
Input: "()())()" Output: ["()()()", "(())()"]
Example2:
Input: "(a)())()" Output: ["(a)()()", "(a())()"]
Example3:
Input: ")(" Output: [""]
Clarification:
The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note:
Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
解题思路
- 这道题首先可以用 BFS 来解
- 我把给定字符串排入队中，然后取出检测其是否合法，若合法直接返回，
- 不合法的话，对其进行遍历，
- 对于遇到的左右括号的字符，去掉括号字符生成一个新的字符串，如果这个字符串之前没有遇到过，将其排入队中，用 HashSet 记录一个字符串是否出现过。
- 对队列中的每个元素都进行相同的操作，直到队列为空还没找到合法的字符串的话，那就返回空集
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
queue<string> q({s});
unordered_set<string> visited({s});
bool found = false;
while(!q.empty()){
string str = q.front();
q.pop();
if(isValid(str)){
res.push_back(str);
found = true;
}
if(found){
continue;
}
for(int i = 0; i < str.size(); i++){
if(str[i] != '(' && str[i] != ')'){ // 字符串有可能是这种形式 "(a)())()"
continue;
}
string t = str.substr(0, i) + str.substr(i + 1);
if(!visited.count(t)){
q.push(t);
visited.insert(t);
}
}
}
return res;
}
bool isValid(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;
}
};
