301. 删除无效的括号
给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
- 示例 1:
输入:s = “()())()”
输出:["(())()","()()()"]
- 示例 2:
输入:s = “(a)())()”
输出:["(a())()","(a)()()"]
- 示例 3:
输入:s = “)(”
输出:[""]
提示:
- 1 <= s.length <= 25
- s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
- s 中至多含 20 个括号
解题思路
使用广度优先搜索,对上一次产生的字符串的每个括号,逐个尝试删除,每次bfs等于删除一个括号,当出现合法的字符串时,就将其加入结果数组
代码
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
unordered_set<string> set;
set.insert(s);
while (true) {
for (string t:set) {
if (is_valid(t))
res.push_back(t);
}
if (res.size() > 0)
return res;
unordered_set<string> new_set;
for (string t:set) {
for (int i = 0; i < t.length(); ++i) {
if (t[i]=='('||t[i]==')')
new_set.insert(t.substr(0,i)+t.substr(i+1));
}
}
set=new_set;
}
return res;
}
bool is_valid(string s) {
int l = 0;
for (char c:s) {
if (c == '(')
l++;
else if (c == ')')
l--;
if (l < 0)
return false;
}
return l==0;
}
};