Given a balanced parentheses string
S, compute the score of the string based on the following rule:
()has score 1ABhas scoreA + B, where A and B are balanced parentheses strings.(A)has score2 * A, where A is a balanced parentheses strings
Example 1:
Input: "()"
Output: 1Example 2:
Input: "(())"
Output: 2Example 3:
Input: "()()"
Output: 2Example 4:
Input: "(()(()))"
Output: 6
Note:
Sis a balanced parentheses string, containing only(and).2 <= S.length <= 50
Approach #1. DFS. [Java]
class Solution {
public int scoreOfParentheses(String S) {
return helper(S, 0, S.length() - 1);
}
public int helper(String S, int l, int r) {
if (l + 1 == r) return 1;
int b = 0;
for (int i = l; i < r; ++i) {
if (S.charAt(i) == '(') b++;
else b--;
if (b == 0) return helper(S, l, i) + helper(S, i+1, r);
}
return 2 * helper(S, l + 1, r - 1);
}
}
Approach #2: Stack. [Java]
class Solution {
public int scoreOfParentheses2(String S) {
boolean mode = true;
int ret = 0;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < S.length(); ++i) {
if (S.charAt(i) == ')' && mode) {
ret += Math.pow(2, stack.size() - 1);
mode = false;
stack.pop();
} else if (S.charAt(i) == '(') {
stack.push('(');
mode = true;
} else {
stack.pop();
}
}
return ret;
}
}