Given a balanced parentheses string
S
, compute the score of the string based on the following rule:
()
has score 1AB
has 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: 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
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; } }