1249. Minimum Remove to Make Valid Parentheses

找到沒辦法互相成雙成對的括號, 把它給移除

這邊前面挑括號的方式就只是假設遇到左括號 就丟進stack, 並且在遇到右括號就pop, 其餘都記下來

最後在重新把這些被記下來的index給挑掉, 但我的作法在最後一部是O(n²)

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> left_p_index;
        vector<int> remove_index;
        for(int i = 0; i < s.size();i++){
            if(s[i] == '('){
                left_p_index.push(i);
            }else if(s[i] ==')'){
                if(left_p_index.empty()){
                    remove_index.push_back(i);
                }else{
                    left_p_index.pop();
                }
            }
        }
        while(!left_p_index.empty()){
            remove_index.push_back(left_p_index.top());
            left_p_index.pop();
        }
        string res = "";
        for(int i = 0; i < s.size(); i++){
            if(find(remove_index.begin(), remove_index.end(), i) == remove_index.end()){
                res += s[i];
            }
        }
        return res;
    }
};

有個更快的方法, 他當錯誤我們把它換成一個奇怪的字符, 就能用O(n)的時間掃除了

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> left_p_index;
        for(int i = 0; i < s.size();i++){
            if(s[i] == '('){
                left_p_index.push(i);
            }else if(s[i] ==')'){
                if(left_p_index.empty()){
                    s[i] = '?';
                }else{
                    left_p_index.pop();
                }
            }
        }
        while(!left_p_index.empty()){
            s[left_p_index.top()] = '?';
            left_p_index.pop();
        }
        string res = "";
        for(int i = 0; i < s.size(); i++){
            if(s[i] != '?'){
                res+=s[i];
            }
        }
        return res;
    }
};