【LeetCode】1021. Remove Outermost Parentheses 解题报告（Python）

作者：负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

题目描述

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:

S.length <= 10000
S[i] is “(” or “)”
S is a valid parentheses string

题目大意

找出字符串中每对括号匹配的结果去除最外层的()之后的结果之和。

解题方法

遍历

看到括号匹配，大家一般都想到用一个栈，其实不用栈也可以。

我们只需要一个变量count保存左括号数-右括号数即可。即遇到左括号则自增1，遇到右括号则自减1.当count为0的时候，说明在这一段中左括号和右括号相等，是个完美匹配的括号串了。

我们使用一个变量previ保存的是上一次括号完全匹配之后，下一个括号匹配开始位置。由于这个题需要让我们把最外层的括号去掉，所以，当count==0的时候，我们把结果增加的是[previ + 1, i)，左闭右开区间。

Python代码如下：

class Solution(object):

    def removeOuterParentheses(self, S):

        """

        :type S: str

        :rtype: str

        """

        previ = 0

        res = ""

        count = 0

        for i, s in enumerate(S):

            if s == '(':

                count += 1

            else:

                count -= 1

            if count == 0:

                res += S[previ + 1: i]

                previ = i + 1

        return res

日期

2019 年 4 月 7 日 —— 周赛bug了3次。。

巴特西

【LeetCode】1021. Remove Outermost Parentheses 解题报告（Python）

目录

题目描述

题目大意

解题方法

遍历

日期

最新文章

热门文章