class Solution {
public:
int scoreOfParentheses(string s) {
}
};
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原站题解
python3 解法, 执行用时: 36 ms, 内存消耗: 14.9 MB, 提交时间: 2022-10-09 09:39:29
class Solution:
def scoreOfParentheses(self, s: str) -> int:
n = len(s)
if n == 2:
return 1
bal = 0
for i, c in enumerate(s):
bal += 1 if c == '(' else -1
if bal == 0:
if i == n - 1:
return 2 * self.scoreOfParentheses(s[1:-1])
return self.scoreOfParentheses(s[:i + 1]) + self.scoreOfParentheses(s[i + 1:])
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-10-09 09:38:26
class Solution:
def scoreOfParentheses(self, s: str) -> int:
st = [0]
for c in s:
if c == '(':
st.append(0)
else:
v = st.pop()
st[-1] += max(2 * v, 1)
return st[-1]
python3 解法, 执行用时: 32 ms, 内存消耗: 15 MB, 提交时间: 2022-10-09 09:36:23
class Solution:
def scoreOfParentheses(self, s: str) -> int:
ans = bal = 0 # bal为每个(的深度
for i, c in enumerate(s):
bal += 1 if c == '(' else -1
if c == ')' and s[i - 1] == '(':
ans += 1 << bal
return ans