删除最外层的括号

难度: Easy

有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。

例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。

示例 1：

输入：s = "(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2：

输入：s = "(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：

输入：s = "()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。

提示：

1 <= s.length <= 10⁵
s[i] 为 '(' 或 ')'
s 是一个有效括号字符串

Submission

运行时间: 26 ms

内存: 15.9 MB

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        res, stack = '', []
        for ch in s:
            if ch == '(':
                if stack:
                    res += ch
                stack.append(ch)
            else:
                stack.pop()
                if stack:
                    res += ch
        return res

Explain

这个题解的思路是使用一个栈来辅助删除最外层的括号。遍历输入字符串，对于每个字符，如果是左括号 '('，则判断栈是否为空，如果不为空，说明这个左括号不是最外层的括号，因此需要将它添加到结果字符串中；然后将这个左括号入栈。如果是右括号 ')'，则先出栈一个左括号，然后判断栈是否为空，如果不为空，说明这个右括号不是最外层的括号，因此需要将它添加到结果字符串中。最终返回结果字符串。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        res, stack = '', []  # 初始化结果字符串和辅助栈
        for ch in s:
            if ch == '(':  # 如果是左括号
                if stack:  # 如果栈不为空，说明这个左括号不是最外层的
                    res += ch
                stack.append(ch)  # 将左括号入栈
            else:  # 如果是右括号
                stack.pop()  # 出栈一个左括号
                if stack:  # 如果栈不为空，说明这个右括号不是最外层的
                    res += ch
        return res  # 返回结果字符串

Explore

栈是一种先进后出（LIFO）的数据结构，非常适合处理嵌套结构，如括号匹配问题。这是因为最新加入的左括号必须与接下来遇到的第一个右括号匹配，这与栈的操作特性完全一致。相比之下，队列是先进先出（FIFO）的结构，不适合这种类型的匹配问题，因为它无法灵活地访问最近加入的元素。链表虽然可以从任何位置增加或删除节点，但在此问题中使用链表进行操作会增加不必要的复杂性和开销，因为我们仅需要简单的后进先出操作。

在算法中，每当遇到一个左括号 '('，会先判断栈是否为空。如果栈不为空，意味着当前左括号是内层括号的一部分，因此应该将其加入到结果字符串中。然后无论栈是否为空，都将该左括号入栈。对于每个右括号 ')'，首先将栈顶的左括号出栈，然后再次检查栈是否为空。如果栈不为空，表明当前右括号也是内层括号的一部分，因此将其添加到结果字符串中。这种方式确保只有非最外层的括号被加入到结果字符串中。

算法通过栈的特性来跟踪每个原语的开头和结束。对于输入 '(()())(())'，每当栈从非空变为空时，表明一个原语的最外层括号匹配完成。算法通过在栈为空时不添加括号到结果字符串来确保最外层的括号不被包括，而只有内层括号被添加。因此，每个原语被正确处理，其最外层的括号被排除。

对于输入 '()()()'，这个字符串实际上是由多个已经没有外层括号的最小单位括号构成的。在这种情况下，算法在处理每对括号时，栈会先入栈一个左括号然后马上出栈，因此每次栈的状态都会从非空变为空，导致不会有任何括号被添加到结果字符串中。所以，算法的输出将是一个空字符串，这是正确的处理结果。