1249. Minimum Remove to Make Valid Parentheses

https://leetcode.com/contest/weekly-contest-161/problems/minimum-remove-to-make-valid-parentheses/

Remove the minimum number of invalid parentheses in order to make the input string valid. Return one possible results.

Note: The input string may contain letters other than the parentheses(and).

Thoughts

由()和字母组成的字符串，返回任意一个最少删除字符能够适得()配对的结果。301的简化版, 只要返回一个不需要DFS，核心思想还是一致的。 当count < 0时意味着par[1]数目超过par[0], 可以删除prefix中的任意一个par[1], 删除i。当par[0] == '('时, 意味着多出的'('还没有删, 因此把上轮删的结果的s翻转一下, 把par[0]换成')', 重复之前的过程。 此时s中是配好对的了, 只是顺序还是反着的, 最后再把s翻转。

Code

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        int r = 0;
        string res;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') ++r;
            else if (s[i] == ')') --r;
            if (r >= 0) {
                res.push_back(s[i]);
            } else ++r;
        }
        s = res;
        res.clear();
        r = 0;
        for (int i = s.length() - 1; i >= 0; --i) {
            if (s[i] == ')') ++r;
            else if (s[i] == '(') --r;
            if (r >= 0) {
                res.push_back(s[i]);
            } else ++r;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Analysis

Errors:

1. 当count--到小于0时, 别忘了再把它加回去. 因为相当于删除了i, count又平衡了.

时间复杂度O(N).