LeetCode 1021. 删除最外层的括号缩略图

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

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

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

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

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

1021. 删除最外层的括号 – 力扣(Leetcode)

LeetCode 1021. 删除最外层的括号插图
OpenCV步步精深-可心科创工作室

提示:

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

思路:

栈,但是要记录索引。

python3实现:

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        # 用栈,找到各个组,去除最外层括号
        p = 0
        need_to_del = []
        stack = []

        while p <= len(s) - 1:
            if s[p] == ")":
                # 删掉栈最后一个元素
                stack.pop()
                if len(stack) == 0:
                    need_to_del.append(p)

            else:
                if  len(stack) == 0:
                    need_to_del.append(p)
                stack.append("(")
            p += 1
        #print("need_to_del:", need_to_del)        
        
        result = ""
        for i in range(len(s)):
            if i in need_to_del:
                pass
            else:
                result += s[i]
        return result
LeetCode 1021. 删除最外层的括号插图1
OpenCV步步精深-可心科创工作室

更多干货见 OpenCV步步精深

作者 admin

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注