LeetCode 856. 括号的分数
题目描述
题意分析
给定合法的平衡括号串，按三条规则计分：
()得 1 分，两个平衡串并列时分数相加，在一个非空平衡串外包一对括号时分数翻倍。不必真的保存每层子表达式的分数，可以把最终得分拆成每个最内层
()对答案的贡献。
解法：按深度累加基础 () 贡献
核心思路
[!blue]
基础括号对
()自身产生 1 分，每多包一层括号，它的贡献就乘以 2。若它外面还有d层括号，最终贡献就是2^d。并列结构的分数相加，而外层的乘二可以分配到内部每一项上，因此整个字符串的分数就是所有基础()贡献之和。扫描时用
depth记录尚未闭合的左括号数。遇到左括号就加一，遇到右括号先减一：此时它对应的这一对括号已经闭合，剩下的depth恰好是外面仍包着它的层数。只有右括号的前一个字符是左括号时，当前闭合的才是基础
()，这时将1 << depth加入答案。若前一个字符也是右括号，说明当前闭合的是外层括号；它的翻倍作用早已体现在里面各个基础对的深度中，不能再计一次分。每个基础对都在自己的右括号处计算一次，没有漏掉并列部分，也没有重复计算外层，因此只维护深度和总分即可。
解题步骤
- 初始化
depth = 0、score = 0，从左到右扫描字符串。- 遇到
(，将深度加一。- 遇到
)，先将深度减一，再检查前一个字符是否为(。- 若构成基础
()，将2^depth，即1 << depth，加入score。- 扫描完毕返回
score。题目保证括号串合法，所有基础对都能按上述方式识别。
代码实现
class Solution {
public int scoreOfParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int depth = 0;
int score = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') {
depth++;
} else {
// 先回到外层深度，再结算基础空括号对
depth--;
if (i > 0 && s.charAt(i - 1) == '(') {
score += 1 << depth;
}
}
}
return score;
}
}
func scoreOfParentheses(s string) int {
if len(s) == 0 {
return 0
}
score := 0
depth := 0
for i := 0; i < len(s); i++ {
if s[i] == '(' {
depth++
} else {
// 先回到外层深度，再结算基础空括号对
depth--
if i > 0 && s[i-1] == '(' {
score += 1 << depth
}
}
}
return score
}
复杂度分析
- 时间复杂度：$O(n)$，
n为字符串长度，每个括号处理一次。- 空间复杂度：$O(1)$，只维护当前深度和累计分数，不需要栈。
关键点总结
[!green]
- 基础
()产生 1 分，所有包裹它的外层括号共同决定乘二次数。- 右括号先让深度减一，得到的才是基础对以外的层数。
- 只给基础对计分，外层括号的作用已经包含在这些贡献中。
易错点总结
[!yellow]
- 先计分再减深度：会把基础括号对自身也算成外包层，让贡献多乘一次 2。
- 每个右括号都计分：会把已经通过深度计算过的外层作用重复加入。
- 只统计最深的一个基础对：并列部分都对答案有贡献，需要累计所有基础对。
- 只按整体最大深度算分：相同最大深度的字符串可以包含不同数量的基础对，最大深度不足以决定总分。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 20. 有效的括号 | 简单 | 括号匹配提供嵌套结构，本题还要按基本对、并列相加与嵌套翻倍规则计算分数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！