LeetCode 题解工作台
括号的分数
给定一个平衡括号字符串 S ，按下述规则计算该字符串的分数： () 得 1 分。 AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。 (A) 得 2 * A 分，其中 A 是平衡括号字符串。 示例 1： 输入： "()" 输出： 1 示例 2： 输入： "(())" 输出： 2 示例 3…
2
题型
4
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
我们通过观察发现，`()` 是唯一贡献分数的结构，外括号只是为该结构添加了一些乘数。所以我们只需要关心 `()`。 我们用 维护当前括号的深度，对于每个 `(`，我们将深度加一，对于每个 `)`，我们将深度减一。当我们遇到 `()` 时，我们将 加到答案中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
()得 1 分。AB得A + B分，其中 A 和 B 是平衡括号字符串。(A)得2 * A分，其中 A 是平衡括号字符串。
示例 1：
输入： "()" 输出： 1
示例 2：
输入： "(())" 输出： 2
示例 3：
输入： "()()" 输出： 2
示例 4：
输入： "(()(()))" 输出： 6
提示：
S是平衡括号字符串，且只含有(和)。2 <= S.length <= 50
解题思路
方法一：计数
我们通过观察发现，() 是唯一贡献分数的结构，外括号只是为该结构添加了一些乘数。所以我们只需要关心 ()。
我们用 维护当前括号的深度，对于每个 (，我们将深度加一，对于每个 )，我们将深度减一。当我们遇到 () 时，我们将 加到答案中。
我们举个实际的例子，以 (()(())) 为例，我们首先找到内部两个闭合括号 ()，然后将分数加上对应的 。实际上，我们是在计算 (()) + ((())) 的分数。
( ( ) ( ( ) ) )
^ ^ ^ ^
( ( ) ) + ( ( ( ) ) )
^ ^ ^ ^
时间复杂度 ，空间复杂度 。其中 是字符串的长度。
括号相关类型题：
class Solution:
def scoreOfParentheses(self, s: str) -> int:
ans = d = 0
for i, c in enumerate(s):
if c == '(':
d += 1
else:
d -= 1
if s[i - 1] == '(':
ans += 1 << d
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an efficient stack-based solution to manage nested structures.
- question_mark
Evaluate how the candidate handles multiple nested parentheses and their score computation.
- question_mark
Focus on correct state management using the stack, ensuring the solution works for all string lengths.
常见陷阱
外企场景- error
Mismanaging nested parentheses by not properly doubling the inner score.
- error
Forgetting to add the scores when encountering non-nested parentheses like '()()'.
- error
Incorrect stack operations that lead to incorrect score accumulation.
进阶变体
外企场景- arrow_right_alt
Modify the problem to handle non-balanced parentheses strings and test for validity.
- arrow_right_alt
Optimize the solution to handle larger strings by managing stack size more effectively.
- arrow_right_alt
Consider variations where parentheses are nested with different operations or values.