数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中移除无效括号
假设我们有一串括号。我们必须移除最少数量的无效括号并返回格式良好的括号字符串。因此，如果输入类似于“()(()()”，则结果将是[“()()()”,“()(())”]。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为solve()的方法，它将接收pos、left、right、l、r、字符串数组res和字符串temp作为参数。
如果pos等于s的大小，则：
如果left等于0且right等于0，则：
如果(m[temp]不等于零)为假，则：
将temp插入res的末尾
m[temp] := 1
返回
如果s[pos]等于'('且right > 0，则：
调用solve(pos + 1, left, right - 1, l, r, res, temp + 空字符串)
否则，如果s[pos]等于')'且left > 0，则：
调用solve(pos + 1, left - 1, right, l, r, res, temp + 空字符串)
如果s[pos]等于'('，则：
调用solve(pos + 1, left, right, l + 1, r, res, temp + "(")
否则，如果s[pos]等于')'且l > r，则：
调用solve(pos + 1, left, right, l, r + 1, res, temp + ')')
如果s[pos]不等于'('且s[pos]不等于')'，则：
调用solve(pos + 1, left, right, l, r, res, temp + s[pos])
在主方法中执行以下操作：
创建一个数组res
l := 0, r := 0
初始化i := 0，当i < s的大小时，i递增1：
如果s[i]等于'('，则：
r递增1
否则，如果s[i]等于')'，则：
如果r不等于零，则r递减1
否则l递增1
调用函数solve(0,l,r,0,0,res)
返回res
示例
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
string s;
map <string ,int> m;
void solve(int pos, int left, int right,int l, int r, vector <string> &res, string temp=""){
if(pos == s.size()){
if(left==0 && right==0 && l==r){
if(!m[temp])
res.push_back(temp);
m[temp] = 1;
}
return;
}
if(s[pos] =='(' && right>0 ){
solve(pos+1,left,right-1,l,r,res,temp+"");
} else if(s[pos] ==')' && left>0) {
solve(pos+1,left-1,right,l,r,res,temp+"");
}
if(s[pos] =='(')solve(pos+1,left,right,l+1,r,res,temp+"(");
else if(s[pos] == ')' && l>r)solve(pos+1,left,right,l,r+1,res,temp+')');
if(s[pos]!='(' && s[pos]!=')')solve(pos+1,left,right,l,r,res,temp+s[pos]);
}
vector<string> removeInvalidParentheses(string s) {
vector <string > res;
int l = 0;
int r=0;
this->s = s;
for(int i =0;i<s.size();i++){
if(s[i] == '('){
r++;
} else if(s[i]==')') {
if(r)r--;
else l++;
}
}
solve(0,l,r,0,0,res);
return res;
}
};
main(){
Solution ob;
print_vector(ob.removeInvalidParentheses("()(()()"));
}输入
“()(()()”
输出
[()()(), ()(()), ]
276 次浏览
