856. 括号的分数
问题描述
给定一个平衡括号字符串s，按下述规则计算该字符串的分数：
()得 1 分AB得A + B分，其中A和B是平衡括号字符串(A)得2 * A分，其中A是平衡括号字符串
返回字符串s的分数。
示例：
输入:"()"输出:1输入:"(())"输出:2解释:(())=2*()=2*1=2输入:"()()"输出:2解释:()()=()+()=1+1=2输入:"(()(()))"输出:6解释:(()(()))=2*(()+(()))=2*(1+2)=6算法思路
深度优先搜索 + 栈模拟：
核心：
- 平衡括号字符串可以递归分解
- 每个
()贡献的分数 = 2^(深度)
方法一：递归
- 遍历字符串，找到每个独立的平衡子串
- 对每个子串递归计算分数
- 合并结果：独立子串相加，嵌套子串乘以2
方法二：深度计算
- 遍历字符串，维护当前深度
- 遇到
()时，贡献分数为 2^depth - 每个
()的实际贡献等于它所在深度的2的幂次
方法三：栈模拟
- 使用栈存储当前各层的分数
- 遇到
(时压入0 - 遇到
)时，计算当前层分数并更新上一层
代码实现
方法一：递归
classSolution{/** * 递归计算括号字符串的分数 * 将字符串分解为独立的平衡子串，分别计算后相加 * * @param s 平衡括号字符串 * @return 字符串的分数 */publicintscoreOfParentheses(Strings){returnscore(s,0,s.length()-1);}/** * 计算子串s[start...end]的分数 */privateintscore(Strings,intstart,intend){// 基础情况：最简单的"()"得1分if(end-start==1){return1;}intbalance=0;// 平衡计数器inttotalScore=0;// 找到独立的平衡子串并分别计算for(inti=start;i<=end;i++){if(s.charAt(i)=='('){balance++;}else{balance--;}// 当balance为0时，找到了一个独立的平衡子串if(balance==0){if(i==end){// 整个字符串是一个嵌套结构：(A)// 分数 = 2 * score(A)totalScore=2*score(s,start+1,end-1);}else{// 当前子串是独立的：AB 形式// 分数 = score(A) + score(B)totalScore+=score(s,start,i);// 递归处理剩余部分totalScore+=score(s,i+1,end);break;// 已经分解完成}}}returntotalScore;}}方法二：深度计算
classSolution{/** * 深度计算 * 每个"()"的贡献是2^depth，其中depth是其嵌套深度 * * @param s 平衡括号字符串 * @return 字符串的分数 */publicintscoreOfParentheses(Strings){intdepth=0;// 当前嵌套深度inttotalScore=0;// 总分数for(inti=0;i<s.length();i++){if(s.charAt(i)=='('){depth++;}else{depth--;// 如果前一个字符是'('，说明遇到了"()"if(s.charAt(i-1)=='('){// 贡献分数为2^depthtotalScore+=(1<<depth);// 位运算：1 << depth = 2^depth}}}returntotalScore;}}方法三：栈模拟
importjava.util.*;classSolution{/** * 使用栈模拟计算括号分数 * 栈中存储当前各层的累计分数 * * @param s 平衡括号字符串 * @return 字符串的分数 */publicintscoreOfParentheses(Strings){Stack<Integer>stack=newStack<>();stack.push(0);// 初始化栈底为0for(charc:s.toCharArray()){if(c=='('){// 遇到左括号，压入0表示新层开始stack.push(0);}else{// 遇到右括号，计算当前层的分数intcurrentScore=stack.pop();// 当前层的分数intparentScore=stack.pop();// 父层的分数// 如果currentScore为0，说明是"()"，得1分// 否则是嵌套结构，得2 * currentScore分intlayerScore=currentScore==0?1:2*currentScore;// 将当前层分数加到父层stack.push(parentScore+layerScore);}}// 栈中只剩最终结果returnstack.pop();}}算法分析
- 方法一时间复杂度：O(n²)
- 最坏情况下每次递归都要遍历整个子串
- 例如：
(((((...)))))这样的完全嵌套结构
- 方法二时间复杂度：O(n)
- 只需要一次遍历
- 位运算操作是O(1)
- 方法三时间复杂度：O(n)
- 每个字符最多入栈出栈一次
- 空间复杂度：
- 方法一：O(n)（递归栈）
- 方法二：O(1)
- 方法三：O(n)（显式栈）
算法过程
1：s = "(()(()))"
方法二：
s: ( ( ) ( ( ) ) ) i: 0 1 2 3 4 5 6 7- i=0：
(，depth=1 - i=1：
(，depth=2 - i=2：
)，depth=1，前一个字符是(，所以totalScore += 2^1 = 2 - i=3：
(，depth=2 - i=4：
(，depth=3 - i=5：
)，depth=2，前一个字符是(，所以totalScore += 2^2 = 4 - i=6：
)，depth=1，前一个字符是)，不加分 - i=7：
)，depth=0，前一个字符是)，不加分
结果：totalScore = 2 + 4 = 6
方法三：
初始: stack = [0] ( : stack = [0, 0] ( : stack = [0, 0, 0] ) : pop 0, pop 0 → 0==0 → push 0+1 = [0, 1] ( : stack = [0, 1, 0] ( : stack = [0, 1, 0, 0] ) : pop 0, pop 0 → 0==0 → push 0+1 = [0, 1, 1] ) : pop 1, pop 1 → 1!=0 → push 1+2*1 = [0, 3] ) : pop 3, pop 0 → 3!=0 → push 0+2*3 = [6] 结果: 6测试用例
publicclassMain{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：基础情况System.out.println("Test 1: "+solution.scoreOfParentheses("()"));// 1// 测试用例2：嵌套System.out.println("Test 2: "+solution.scoreOfParentheses("(())"));// 2// 测试用例3：并列System.out.println("Test 3: "+solution.scoreOfParentheses("()()"));// 2// 测试用例4：复杂嵌套System.out.println("Test 4: "+solution.scoreOfParentheses("(()(()))"));// 6// 测试用例5：深度嵌套System.out.println("Test 5: "+solution.scoreOfParentheses("((()))"));// 4// ((())) = 2 * (2 * ()) = 2 * 2 * 1 = 4// 测试用例6：混合结构System.out.println("Test 6: "+solution.scoreOfParentheses("()(())"));// 3// ()(()) = 1 + 2 = 3// 测试用例7：更复杂System.out.println("Test 7: "+solution.scoreOfParentheses("(()()())"));// 6// (()()()) = 2 * (1 + 1 + 1) = 6// 测试用例8：最大深度System.out.println("Test 8: "+solution.scoreOfParentheses("((((()))))"));// 16// 2^4 = 16// 测试用例9：单层多并列System.out.println("Test 9: "+solution.scoreOfParentheses("()()()()"));// 4// 测试用例10：嵌套和并列混合System.out.println("Test 10: "+solution.scoreOfParentheses("((())(()))"));// 8// ((())(())) = 2 * (2 + 2) = 8}}关键点
深度贡献：
- 每个
()的实际贡献是2^depth - 每嵌套一层，外层的括号会将内层分数乘以2
- 每个
识别
()：- 在遍历时，如果当前字符是
)且前一个字符是(，说明遇到了基础的()
- 在遍历时，如果当前字符是
位运算：
1 << depth比Math.pow(2, depth)更高效- 位运算在底层执行更快
常见问题
为什么每个
()的贡献是 2^depth？
每层外层括号都会将内层分数乘以2。例如，深度为2的()会被外层两层括号分别乘以2，总共乘以4=2²。方法二如何处理
()()这种并列情况？
每个()都会被独立识别和计算。第一个()在深度0时贡献1，第二个()也在深度0时贡献1，总共2。栈中的初始0？
初始0作为根节点的分数，确保所有计算都有父层可以累加。最终栈中只剩这个累加后的总分数。
