LeetCode 1249. Minimum Remove to Make Valid Parentheses

题目

原题在此

解析

用stack记录出现过的括号, 遇到左括号就入栈括号的位置; 遇到右括号时, 若栈不为空则可构成合法括号, 出栈一个元素; 否则将当前位值标注为待删除. 最后将栈内剩余元素(没有右括号可以匹配的左括号)全部标记待删除. 最后调用string::erase()方法或其他语言的类似方法一次全部删除.

代码

c++

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> stk;
        int n = s.size();
        for(int i = 0; i < n; ++i) {
            if(s[i] == '(') stk.push(i);
            if(s[i] == ')') {
                if(stk.empty()) s[i] = '!';
                else stk.pop();
            }
        }
        
        while(!stk.empty()) {
            s[stk.top()] = '!';
            stk.pop();
        }
        
        s.erase(std::remove(s.begin(), s.end(), '!'), s.end());
        return s;
    }
};