删除C ++中的无效括号

假设我们有一串括号。我们必须删除最少数量的无效括号并返回格式正确的括号字符串，因此，如果输入类似于“()（()()”，那么结果将是[“()()()”，“（ ）（()）”]

为了解决这个问题，我们将遵循以下步骤-

• 定义一个名为solve()的方法，它将接受pos、left、right、l、r、string array res和string temp。

• 如果pos与s的大小相同，则，

• 如果left等于0，right等于0，那么，

• 如果（m[temp]非零）为假，则，

• res末端插入temp

• m[temp]：=1

• return
  

• 如果s[pos]与“（”相同且右>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[位置]与“）”相同且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的大小增加1

• 如果s[i]与“（”相同，则，

• r增加1

• 否则，当s[i]与“）”相同时，则-

• 如果r非零，则将r减1

• 将else 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("()(()()"));
}

输入值

“()(()()”

输出结果

[()()(), ()(()), ]