1021删除最外层得括号

1021 删除最外层的括号

下面是题目

下面是模板

class Solution {
public:
    string removeOuterParentheses(string S) {
       
    }
};

我自己是没有办法想出很妙的算法的

class Solution {
public:
    string removeOuterParentheses(string S) {
        int L=1;int R=0;
        string ans;
        //因为我们的前提是：S是一个有效括号的字符串，所以不存在(()之类的情况
        //所以说，括号之内的部分，都是一一匹配的
        //这样，只要没遍历到最外层的括号，那么里面的左右括号数目都是相等的
        //如果左右括号一一匹配，那么L,R的永远不可能相等，这时候把内容压入数组中
        //什么时候会相等？就是当读到最外层括号的时候，R++
        //这时候，L==R就说明了已经匹配到，可以进行下一次匹配
        for(int i=1;i<S.size();i++){
            if(S[i]=='(')
                L++;
            else//因为不是左括号就是右括号
                R++;
            if(R!=L)
                ans.push_back(S[i]);
            else {
                //重置。进行下一次寻找
                i++;L=1;R=0;
            }
        }
        return ans;
    }
};

万变不离其宗，其他方法也是如此，但我认为还是第一种方法最简洁

class Solution {
public:
    string removeOuterParentheses(string S) {
        int cnt = 0;
        string res;
        for (auto c:S) 
        {
            //如果看到左括号，cnt++，否则cnt--,相当于上面的L++,R++
            if(c == '('){
                cnt++;
            //这里特别要注意，当读取到第一个左括号的时候，就直接continue，不让他压入数组
                if(cnt == 1) continue;
            }
            else cnt--;
            //当cnt再次回到0的时候，就是读取到最外层的括号的时候，所以两种情况不会进行下一步
            //一种就是读取最外层（ 时，直接continue；还有是读取）时，cnt=0。
            if(cnt != 0)res.push_back(c);
        }
        return res;
    }
};