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

解法

使用一个栈记录最外层括号的状态

保证栈中只有最外层的左括号，然后把内部的括号依次存入一个列表里，使用 count 记录内部左括号的数目，每遇到一个左括号 count 的值就加一，遇到一个右括号 count 的值减一。当遇到一个右括号并且 count 为0时到达最外层的右括号，此时将栈中的左括号 pop 出去即可。

()((()))	stack	final	count
(	(		0
)			0
(	(		0
(	(	(	1
(	(	((	2
)	(	(()	1
)	(	(())	0
)		(())	0

class Solution:
    def removeOuterParentheses(self, S: str) -> str:
        # use a stack to record the status
        stack = []
        final = []
        count = 0

        for c in S:
            # outer?
            if not stack:
                stack.append(c)
                continue
            # inner and left parentheses, so append it and count++
            if c == '(':
                final.append(c)
                count += 1
            elif c == ')':
                # still in?
                if count:
                    final.append(c)
                    count -= 1
                # out now
                else:
                    stack.pop()

        return ''.join(final)

一个更简洁的解法

class Solution:
    def removeOuterParentheses(self, S):
        res, opened = [], 0
        for c in S:
            if c == '(' and opened > 0: res.append(c)
            if c == ')' and opened > 1: res.append(c)
            opened += 1 if c == '(' else -1
        return "".join(res)

这个真的写的很棒了。

两种方法的时间复杂度和空间复杂度都是 $O(n)$。