力扣1249.移除无效的括号

力扣1249.移除无效的括号

• 栈 + 哈希表

  • 哈希表存所有待删除的括号下标

•   class Solution {
    public:
        string minRemoveToMakeValid(string s) {
            vector<int> st;
            string res;
            unordered_set<int> cnt;
            for(int i=0;i<s.size();i++)
            {
                if(s[i] == '(')
                    st.push_back(i);
                else if(s[i] == ')')
                {
                    if(st.empty())
                        cnt.insert(i);
                    else
                        st.pop_back();
                }
            }
            while(!st.empty())
            {
                cnt.insert(st.back());
                st.pop_back();
            }
            for(int i=0;i<s.size();i++)
                if(cnt.find(i) == cnt.end())
                    res += s[i];
            return res;
        }
    };