1. 问题描述
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。
示例 1：
输入： "()"
输出： 1
示例 2：
输入： "(())"
输出： 2
示例 3：
输入： "()()"
输出： 2
示例 4：
输入： "(()(()))"
输出： 6
提示：
- S 是平衡括号字符串，且只含有 ( 和 ) 。
2 <= S.length <= 50
2. 题解
方法一、分治
根据题意，一个平衡括号字符串 s 可以被分解为 A+B 或 (A) 的形式，因此可以对 s 进行分解，分而治之。
如何判断 s 应该分解为 A+B 或 (A) 的哪一种呢？将左括号记为 1，右括号记为 −1，如果 s 的某个非空前缀对应的和 bal=0，那么这个前缀就是一个平衡括号字符串。如果该前缀长度等于 s 的长度，那么 s 可以分解为 (A) 的形式；否则 s 可以分解为 A+B 的形式，其中 A 为该前缀。将 s 分解之后，递归地求解子问题，并且 s 的长度为 2 时，分数为 1。
- Java
class Solution {
public int scoreOfParentheses(String s) {
int n = s.length();
if(n == 2){
return 1;
}
int bal = 0, len = 0;
for(int i=0; i<n; i++){
bal += (s.charAt(i) == '('? 1: -1);
if(bal == 0){
len = i+1;
break;
}
}
if(len==n){
return 2*scoreOfParentheses(s.substring(1, n-1));
}else{
return scoreOfParentheses(s.substring(0, len)) + scoreOfParentheses(s.substring(len));
}
}
}
- C++
class Solution {
public:
int scoreOfParentheses(string s) {
if (s.size() == 2) { //Java s.length()
return 1;
}
int bal = 0, n = s.size(), len = 0;
for (int i = 0; i < n; i++) {
bal += (s[i] == '(' ? 1 : -1); //c++ s[i] <> Java s.charAt(i)
if (bal == 0) {
len = i + 1;
break;
}
}
if (len == n) {
return 2 * scoreOfParentheses(s.substr(1, n - 2)); //Java substring
} else {
return scoreOfParentheses(s.substr(0, len)) + scoreOfParentheses(s.substr(len, n - len));
}
}
};
复杂度分析
-
时间复杂度：O(n^2)，其中 n 是字符串的长度。递归深度为 O(n)，每一层的所有函数调用的总时间复杂度都是 O(n)，因此总时间复杂度为 O(n^2)。
-
空间复杂度：O(n^2)。每一层都需要将字符串复制一遍，因此总空间复杂度为 O(n^2)。对于字符串支持切片的语言，空间复杂度为递归栈所需的空间 O(n)。
说明函数区别
C++ 函数s.substr(pos, len)。主要功能是复制子字符串，要求从指定位置开始，并具有指定的长度。如果没有指定长度_Count或_Count+_Off超出了源字符串的长度，则子字符串将延续到源字符串的结尾。
Java 函数public String substring(int beginIndex, [int endIndex])。主要功能是返回字符串的子字符串，beginIndex -- 起始索引（包括）, 索引从 0 开始。endIndex -- 结束索引（不包括）。
方法二、栈
把平衡字符串 s 看作是一个空字符串加上 s 本身，并且定义空字符串的分数为 0。使用栈 st 记录平衡字符串的分数，在开始之前要压入分数 0，表示空字符串的分数。
在遍历字符串 s 的过程中：
-
遇到左括号，那么需要计算该左括号内部的子平衡括号字符串 A 的分数，也要先压入分数 0，表示 A 前面的空字符串的分数。
-
遇到右括号，说明该右括号内部的子平衡括号字符串 A 的分数已经计算出来了，将它弹出栈，并保存到变量 v 中。如果 v = 0，那么说明子平衡括号字符串 A 是空串，(A) 的分数为 1，否则 (A) 的分数为 2v，然后将 (A) 的分数加到栈顶元素上。
遍历结束后，栈顶元素保存的就是 s 的分数。
- Java
class Solution {
public int scoreOfParentheses(String s) {
Deque<Integer> st = new ArrayDeque<Integer>();
st.push(0);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
st.push(0);
} else {
int v = st.pop();
int top = st.pop() + Math.max(2 * v, 1);
st.push(top);
}
}
return st.peek();
}
}
- C++
class Solution {
public:
int scoreOfParentheses(string s) {
stack<int> st;
st.push(0);
for (auto c : s) {
if (c == '(') {
st.push(0);
} else {
int v = st.top(); //访问栈顶
st.pop(); //弹出栈顶
st.top() += max(2 * v, 1);
}
}
return st.top();
}
};
复杂度分析
-
时间复杂度：O(n)，其中 n 是字符串的长度。
-
空间复杂度：O(n)。栈需要 O(n) 的空间。
方法三、计算最终分数和
根据题意，s 的分数与 1 分的 () 有关。对于每个 ()，它的最终分数与它所处的深度有关，如果深度为 bal，那么它的最终分数为 2^bal。统计所有 () 的最终分数和即可。
举例
1）输入： "(())"
( ( ) )
bal = 1 2 1 0
cur_v= —— —— 2 ——
res = 0 0 2 2
2）输入： "()()"
( ) ( )
bal = 1 0 1 0
cur_v= —— 1 —— 1
res = 0 1 1 2
3）输入： "(()(()))"
( ( ) ( ( ) ) )
bal = 1 2 1 2 3 2 1 0
cur_v= —— —— 2 —— —— 4 —— ——
res = 0 0 2 2 2 6 6 6
- Java
class Solution {
public int scoreOfParentheses(String s) {
int bal = 0, n = s.length(), res = 0;
for (int i = 0; i < n; i++) {
bal += (s.charAt(i) == '(' ? 1 : -1);
if (s.charAt(i) == ')' && s.charAt(i - 1) == '(') {
res += 1 << bal;
}
}
return res;
}
}
- C++
class Solution {
public:
int scoreOfParentheses(string s) {
int bal = 0, n = s.size(), res = 0;
for (int i = 0; i < n; i++) {
bal += (s[i] == '(' ? 1 : -1);
if (s[i] == ')' && s[i - 1] == '(') {
res += 1 << bal;
}
}
return res;
}
};
复杂度分析
-
时间复杂度：O(n)，其中 n 是字符串的长度。
-
空间复杂度：O(1)。