leetcode 301. 删除无效的括号-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 301. 删除无效的括号。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.题目

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按任意顺序返回。

2.示例

1）示例 1：
输入：s = “()())()”
输出：[“(())()”,“()()()”]

2）示例 2：
输入：s = “(a)())()”
输出：[“(a())()”,“(a)()()”]

3）示例 3：
输入：s = “)(”
输出：[“”]

4）提示：
1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号

3.分析

使用dfs去搜索当前字符是否要删除，并用栈去维护，看当前字符串是否合法即可

4.代码

class Solution {
public:
stack kh;
int ans=0;
vector sum1,ans1;
map<string,int> map1;
int sum_r[31];
void make_delete(int pos,string s1,string s){
if(poss.size()){
if(!kh.empty()) return;
if(s1.size()>ans)
ans=s1.size();
sum1.push_back(s1);
return;
}
if(s[pos]>=‘a’&&s[pos]<=‘z’){
make_delete(pos+1,s1+s[pos],s);
return;
}
if(s[pos]‘(’){
kh.push(‘(’);
if(sum_r[pos+1]>=kh.size())
make_delete(pos+1,s1+‘(’,s);
kh.pop();
make_delete(pos+1,s1,s);
}
else{
if(kh.empty())
make_delete(pos+1,s1,s);
else{
if(kh.top()!=‘(’) make_delete(pos+1,s1,s);
else{
make_delete(pos+1,s1,s);
kh.pop();
make_delete(pos+1,s1+‘)’,s);
kh.push(‘(’);
}
}
}
}
vector removeInvalidParentheses(string s) {
memset(sum_r,0,sizeof(sum_r));
for(int i=s.size()-1;i>=0;i–)
sum_r[i]=sum_r[i+1]+(s[i]==‘)’);
make_delete(0,“”,s);
for(int i=0;i<sum1.size();i++)
if(sum1[i].size()==ans&&map1.count(sum1[i])==0){
ans1.push_back(sum1[i]);
map1[sum1[i]]=1;
}
return ans1;
}
};文章来源地址https://www.toymoban.com/news/detail-486254.html