Task
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
2
|
Input: "()"
Output: 1
|
1
2
|
Input: "(())"
Output: 2
|
1
2
|
Input: "()()"
Output: 2
|
1
2
|
Input: "(()(()))"
Output: 6
|
Note:
S is a balanced parentheses string, containing only ( and ).2 <= S.length <= 50
Solution
直接递归
- 如下图：
- 将问题分解为三种情形：
()是递归终止条件(A)需脱去两侧括号，对A再次递归(A)(B)需分解为(A)和(B)，分别递归
- 可使用一个计数来检测后两种情形：遍历字符串，遇到
(计数递增，遇到)计数递减
- 若走到倒数第二个元素计数还未变为0，则是第二种情形
- 还未走完全程计数就变为0，则是第三种情形
时间复杂度：
- 最好情形是()()…()()，只需遍历一次即可，时间复杂度O(n)
- 最坏情形是((((…))))，需遍历多次，每次走完全程，时间复杂度O(n^2)
空间复杂度：不需要为每个元素分配对应空间，空间复杂度O(1)- 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Score of Parentheses.
// Memory Usage: 6.1 MB, less than 100.00% of C++ online submissions for Score of Parentheses.
class Solution {
public:
int scoreOfParentheses(string S) {
return score(S,0,S.size()-1);
}
int score(const string &S,int l,int r){
//若r和l相邻，则必是()，终止递归
if(r-l==1) return 1;
int cnt=0;
//从子串第一个字符遍历到倒数第二个字符
for(int i=l;i<r;++i){
if(S[i]=='(') ++cnt;
if(S[i]==')') --cnt;
//若途中计数归零，说明遇到了一对互补的括号，即(A)(B)，进入两个递归
if(cnt==0)
return score(S,l,i)+score(S,i+1,r);
}
//若在遍历子串的过程中未return，则说明没有遇到互补的括号，即(A)，脱去外层括号
return 2*score(S,l+1,r-1);
}
};
|
将原字符串变形
- 将字符串分解为(A)(B)的形式，其中A和B都是(((…)))的形式
- 例如，(()(()()))的结果是2*(1+2*(1+1))，将2全部乘进括号，变为2+4+4，分解为2的幂。即变形后的字符串是(())+((()))+((()))，只需数括号
- 这种分解的项数是由最小单元
()决定的，每个()都是一项，对应的幂为左侧未被)抵消掉的(的数量。
- 因此任务变为：
- 维护
(的计数，遇到(时递增，遇到)时递减
- 当遇到
()时求幂并加到结果上
时间复杂度：只需遍历一次字符串，故是O(n)空间复杂度：除储存结果、计数、循环变量外，未申请额外内存，故是O(1)- 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Score of Parentheses.
// Memory Usage: 6 MB, less than 100.00% of C++ online submissions for Score of Parentheses.
class Solution {
public:
int scoreOfParentheses(string S) {
int ans=0;
int cnt=0;
for(int i=0;i<S.size();++i){
//维护左侧单独的(个数
if(S[i]=='(') ++cnt;
else --cnt;
//遇到()时计算一项2的幂
if(S[i]=='(' && S[i+1]==')')
//使用位移快速计算2的幂
ans+=1<<(cnt-1);
}
return ans;
}
};
|