05 August 2008
给定一个平衡括号字符串 s，返回该字符串的分数。
平衡括号字符串的分数基于以下规则：
”()” 得 1 分。
AB 的得分为 A + B，其中 A 和 B 是平衡括号字符串。
(A) 得分为 2 * A，其中 A 是平衡括号字符串。
1
2
3
4
5
6
7
8
9
10
11
12
Example 1:
Input: s = "()"
Output: 1
Example 2:
Input: s = "(())"
Output: 2
Example 3:
Input: s = "()()"
Output: 2
Time Complexity - O(N)
Spcae Complexity - O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int scoreOfParentheses(String s) {
Stack<Character> st = new Stack<>();
Stack<Integer> vals = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(')
st.push('(');
else {
char remove = st.pop();
if (remove == '(') {
vals.push(1);
} else {
int toadd = 0;
while (remove == '-') {
remove = st.pop();
toadd += 2 * vals.pop();
}
vals.push(toadd);
}
st.push('-');
}
}
int ans = 0;
while (vals.size() > 0)
ans += vals.pop();
return ans;
}
}
Recursion, 空间O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int scoreOfParentheses(String s) {
Stack<Character> st = new Stack<>();
Stack<Integer> vals = new Stack<>();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == '(')
st.push('(');
else{
char remove = st.pop();
if(remove == '('){
vals.push(1);
}else{
int toadd = 0;
while(remove == '-'){
remove = st.pop();
toadd += 2 * vals.pop();
}
vals.push(toadd);
}
st.push('-');
}
}
int ans = 0;
while(vals.size() > 0)
ans += vals.pop();
return ans;
}
}