[LeetCode] 1021. Remove Outermost Parentheses 去除最外层括号


A valid parentheses string is either empty ("")"(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.  For example, """()""(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + ... + P_k, where P_i are primitive valid parentheses strings.

Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.

Example 1:

Input: "(()())(())"
Output: "()()()"
Explanation:
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

Example 2:

Input: "(()())(())(()(()))"
Output: "()()()()(())"
Explanation:
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".

Example 3:

Input: "()()"
Output: ""
Explanation:
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".

Note:

  1. S.length <= 10000
  2. S[i] is "(" or ")"
  3. S is a valid parentheses string

这道题给了一个合法的括号字符串,其可能由多个合法的括号字符子串组成,现在让把所有合法的子串的最外层的括号去掉,将剩下的拼接起来并返回,根据题目给的例子,不难理解题意。LeetCode 中关于括号的题目还是比较多的,比如 Valid ParenthesesValid Parenthesis StringRemove Invalid Parentheses,和 Longest Valid Parentheses 等。大多都是考察如何判断一个括号字符串是否合法,所谓的合法,大致就是左右括号个数要相同,每个右括号前面必须要有对应的左括号,一个比较简单的判断方法就是用一个变量 cnt,遇到左括号则自增1,遇到右括号则自减1,在这过程中 cnt 不能为负,且最后 cnt 必须为0。这道题限定了括号字符串一定是合法的,但也可以用这个方法来找出每个合法的子串部分,遍历字符串S,若当前字符为左括号,则 cnt 自增1,否则自减1。若 cnt 不为0,说明还不是一个合法的括号子串,跳过。否则我们就知道了一个合法括号子串的结束位置,用一个变量 start 记录合法括号子串的起始位置,初始化为0,这样就可以将去除最外层括号后的中间部分直接取出来加入结果 res 中,然后此时更新 start 为下一个合法子串的起始位置继续遍历即可,参见代码如下:


解法一:

class Solution {
public:
    string removeOuterParentheses(string S) {
        string res = "";
        int cnt = 0, start = 0, n = S.size();
        for (int i = 0; i < n; ++i) {
            (S[i] == '(') ? ++cnt : --cnt;
            if (cnt != 0) continue;
            res += S.substr(start + 1, i - start - 1);
            start = i + 1;
        }
        return res;
    }
};

我们也可以写的更简洁一些,并不需要等到找到整个合法括号子串后再加入结果 res,而是在遍历的过程中就加入。因为这里的括号分为两种,一种是合法子串的最外层括号,这种不能加到结果 res,另一种是其他位置上的括号,这种要加到 res。所以只要区分出这两种情况,就知道当前括号要不要加,区别的方法还是根据 cnt,当遇到左括号时,若此时 cnt 大于0,则一定不是合法子串的起始位置,可以加入 res,之后 cnt 自增1;同理,若遇到右括号,若此时 cnt 大于1,则一定不是合法子串的结束位置,可以加入 res,之后 cnt 自减1,参见代码如下:


解法二:

class Solution {
public:
    string removeOuterParentheses(string S) {
        string res;
        int cnt = 0;
        for (char c : S) {
            if (c == '(' && cnt++ > 0) res.push_back(c);
            if (c == ')' && cnt-- > 1) res.push_back(c);
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1021


类似题目:

Valid Parentheses

Valid Parenthesis String

Remove Invalid Parentheses

Longest Valid Parentheses


参考资料:

https://leetcode.com/problems/remove-outermost-parentheses/

https://leetcode.com/problems/remove-outermost-parentheses/discuss/270022/JavaC%2B%2BPython-Count-Opened-Parenthesis

https://leetcode.com/problems/remove-outermost-parentheses/discuss/270566/My-Java-3ms-Straight-Forward-Solution-or-Beats-100


LeetCode All in One 题目讲解汇总(持续更新中...)

上一篇:[PAT乙级]1021 个位数统计 (思路+精简代码)


下一篇:1021 Deepest Root(甲级)