Given a balanced parentheses string s, return the score of the string.
The score of a balanced parentheses string is based on the following rule:
"()"has score1.ABhas scoreA + B, whereAandBare balanced parentheses strings.(A)has score2 * A, whereAis a balanced parentheses string.
Test Cases
Example 1:
Input: s = "()"
Output: 1
Example 2:
Input: s = "(())"
Output: 2
Example 3:
Input: s = "()()"
Output: 2
Solution
class Solution {
public int scoreOfParentheses(String s) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
for(int i=0; i<s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(0);
} else {
int curr = stack.pop();
int prev = stack.pop();
stack.push(prev + Math.max(2*curr, 1));
}
}
return stack.pop();
}
}class Solution:
def scoreOfParentheses(self, s: str) -> int:
stack = [0]
for c in s:
if c == '(':
stack.append(0)
else:
curr, prev = stack.pop(), stack.pop()
stack.append(prev + max(1, 2*curr))
return stack.pop()