最小删除以在C ++中制作有效的括号

Z时代
2024-01-10
分类：综合

假设我们有一个字符串s'（'，'）'和小写英文字符。我们必须删除最小括号（在任何位置的'（'或'）'），以便得到的括号字符串有效并返回任何有效字符串。当满足所有这些条件时，括号字符串有效-

它是空字符串，仅包含小写字符，或者
它可以写为AB（A与B串联）的形式，其中A和B是有效字符串，或者
它可以以(A)的形式编写，其中A是有效字符串。

因此，如果输入类似于“ a）b(c)d”，那么输出将为“ ab(c)d”

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

定义一个堆栈st
对于范围从0到s的i

如果堆栈不为空，则从堆栈弹出，否则s [i] ='*'
如果s [i] ='（'，则将i插入st
否则，当s [i]为'）'时，

虽然st不为空，

s [堆栈的顶部元素] ='*'
从堆栈弹出

ans：=空字符串
当我的范围是0到s的大小– 1

如果s [i]不是'*'，则ans：= ans + s [i]

返回ans

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string minRemoveToMakeValid(string s) {
      stack <int> st;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == '(')st.push(i);
         else if(s[i] == ')'){
            if(!st.empty())st.pop();
            else s[i] = '*';
         }
      }
      while(!st.empty()){
         s[st.top()] = '*';
         st.pop();
      }
      string ans = "";
     for(int i = 0; i < s.size(); i++){
        if(s[i] != '*')ans += s[i];
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}