题目描述

Given a string s of ‘(‘ , ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

样例

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

算法1 (Stack)

用stack维护括号, 用一个数组记录位置是否合法

时间复杂度: $O(n)$

空间复杂度: $O(n)$

C++ 代码

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        int n = s.size();
        stack<int> stk;
        vector<bool> state(n, true);

        for (int i = 0; i < n; i++) {
            if (s[i] == ')') {
                if (stk.empty()) state[i] = false;
                else stk.pop();
            } else if (s[i] == '(') stk.push(i);
        }

        while (!stk.empty()) {
            state[stk.top()] = false;
            stk.pop();
        }

        string res;
        for (int i = 0; i < n; i++) {
            if (state[i]) res += s[i];
        }
        return res;
    }
};

算法2 (两次线性扫描)

followup: 要求除了输出的str以外没有别的extra space

时间复杂度: $O(n)$

空间复杂度: $O(1)$

C++ 代码

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        int n = s.size();
        int cnt = 0;

        for (int i = 0; i < n; i++) {
            if (s[i] == '(') cnt ++;
            else if (s[i] == ')') {
                if (cnt == 0) s[i] = '#';
                else cnt --;
            }
        }

        cnt = 0;
        for (int j = n - 1; j >= 0; j --) {
            if (s[j] == ')') cnt ++;
            else if (s[j] == '(') {
                if (cnt == 0) s[j] = '#';
                else cnt --;
            }
        }

        string res = "";
        for (int i = 0; i < n; i++) {
            if (s[i] != '#')
                res.push_back(s[i]);
        }
        return res;
    }
};