0856：括号的分数（1562 分）

力扣第 90 场周赛第 2 题

题目

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

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

示例 1：

输入： "()"
输出： 1

示例 2：

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

示例 3：

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

示例 4：

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

提示：

1. S 是平衡括号字符串，且只含有 ( 和 ) 。
2. 2 <= S.length <= 50

分析

显然 s 递归地等于子串的和或 2 倍。可以用栈模拟这个过程，一趟解决。

遇到 ‘(’ 时入栈 0，代表下一层的初始分数，遇到 ‘)’ 出栈当前层的分数添加到上一层即可。 注意按规则，若当前层是最简单的 ‘()’，应该为 1 分而不是 0 分。

解答

1
2
3
4
5
6
7
8
9

def scoreOfParentheses(self, s: str) -> int:
    stack = [0]
    for char in s:
        if char == '(':
            stack.append(0)
        else:
            x = stack.pop()
            stack[-1] += max(2*x, 1)
    return stack[0]

24 ms