题目
Given a balanced parentheses string S, compute the score of the string based on the following rule:
() has score 1AB has score A + B, where A and B are balanced parentheses strings.(A) has score 2 * A, where A is a balanced parentheses string.
Example 1:
Input: “()”
Output: 1
Example 2:
Input: “(())”
Output: 2
Example 3:
Input: “()()”
Output: 2
Example 4:
Input: “(()(()))”
Output: 6
Note:
S is a balanced parentheses string, containing only (and).
2 <= S.length <= 50
题目地址
讲解
这道题分类都有点难，可以算在智力题里面。主要是要理解一个套路：
“(()(()))” -> “(())” + “((()))” = 2 + 4
这样就会发现，可以维护一个层数变量，然后遍历的时候，遇到 '(‘ 就加一，遇到 ”)” 就减一，遇到 ”()” 这一对，就相当于找到了一组。然后把找到的所有组相加就行了。
java 代码
class Solution {
public int scoreOfParentheses(String S) {
int d = -1;
int result = 0;
for(int i=0;i<S.length();i++){
d += S.charAt(i)=='(‘?1:-1;
if(S.charAt(i)=='(‘ && S.charAt(i+1)==’)’){
result += 1 << d;
}
}
return result;
}
}