---

0856. 括号的分数

• 标签：栈、字符串
• 难度：中等

题目链接

• 0856. 括号的分数 - 力扣

题目大意

描述：

给定一个平衡括号字符串 $S$，按下述规则计算该字符串的分数：

• () 得 1 分。
• AB 得 $A + B$ 分，其中 $A$ 和 $B$ 是平衡括号字符串。
• (A) 得 $2 \times A$ 分，其中 $A$ 是平衡括号字符串。

要求：

返回该字符串的分数。

说明：

• $S$ 是平衡括号字符串，且只含有 ( 和 )。
• $2 \le S.length \le 50$。

示例：

• 示例 1：

输入： "()()"
输出： 2

• 示例 2：

输入： "(()(()))"
输出： 6

解题思路

思路 1:栈

根据题意,括号的分数计算规则为:

• () 得 1 分
• AB 得 $A + B$ 分
• (A) 得 $2 \times A$ 分

我们可以使用栈来模拟这个过程:

1. 遍历字符串 $s$,用栈来记录每一层的分数。
2. 遇到 ( 时,将 0 压入栈中,表示新的一层开始。
3. 遇到 ) 时:
   • 弹出栈顶元素 $cur$
   • 如果 $cur = 0$,说明是 (),得 1 分
   • 否则说明是 (A),得 $2 \times cur$ 分
   • 将得分加到新的栈顶(上一层)
4. 最后栈中只剩一个元素,即为总分数。

思路 1:代码

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = [0]  # 初始化栈,栈底为 0
        
        for ch in s:
            if ch == '(':
                # 遇到左括号,新的一层开始
                stack.append(0)
            else:
                # 遇到右括号,计算当前层的分数
                cur = stack.pop()
                if cur == 0:
                    # () 的情况,得 1 分
                    score = 1
                else:
                    # (A) 的情况,得 2 * A 分
                    score = 2 * cur
                # 将分数加到上一层
                stack[-1] += score
        
        return stack[0]

思路 1:复杂度分析

• 时间复杂度:$O(n)$,其中 $n$ 是字符串 $s$ 的长度。需要遍历一次字符串。
• 空间复杂度:$O(n)$,栈的空间复杂度最坏情况下为 $O(n)$。