Leetcode 括号的分数 -- 栈

题目描述

leetcode: 856. 括号的分数

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：() 得 1 分。AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。(A) 得 2 * A 分，其中 A 是平衡括号字符串。

示例 1：输入： “()”
输出： 1
示例 2：输入： “(())”
输出： 2
示例 3：输入： “()()”
输出： 2
示例 4：输入： “(()(()))”
输出： 6
提示：S 是平衡括号字符串，且只含有 ( 和 ) 。2 <= S.length <= 50

解法一：括号匹配统计

• 只有连续的左右括号( )才对结果有贡献
• 遇见 ( ，深度n+1，当深度为n，遇见连续的（ ），结果需要加上2^n
• 遇见 ）,深度-1

python代码实现：

class Solution(object):
    def scoreOfParentheses(self, S):
        ans, deep = 0, 0
        for i, x in enumerate(S):
            if x == '(':
                deep += 1
            else:
                deep -= 1
                if S[i-1] == '(':
                    ans += 1 << deep
        return ans

时间复杂度：O(N) ，其中 N 是字符串 S 的长度。
空间复杂度：O(1)。

解法二： 栈

• 构建一个栈
• 如果遇到 ( 就往栈里面添加
• 如果遇到 ) 就去寻找最近的左括号抵消，同时计算里面的分数。
  以(()(()))示例, 栈结构变化如下
  

python代码实现：

class Solution:
    def scoreOfParentheses(self, S: str) -> int:
        count = 0
        stack = [0] #The score of the current frame
        for x in S:
            if x == '(':
                stack.append(0)
            else:
                count = stack.pop()
                stack[-1] += 1 if count == 0 else 2*count
        return stack.pop()

时间复杂度：O(N)，其中 N是字符串 S 的长度。
空间复杂度：O(N)，为栈的大小。