856. Score of Parentheses

February 26, 2022

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 score 1.
AB 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: Input: s = “()” Output: 1 Example 2: Input: s = “(())” Output: 2 Example 3: Input: s = “()()” Output: 2

code

class Solution {
    public int scoreOfParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.offerLast(0);
        for (char c: s.toCharArray()){
            if (c == '('){
                stack.offerLast(0);
            }else{
                int last = stack.pollLast();
                int before = stack.pollLast();
                // if (last == 0){
                //     stack.offerLast(before + 1);
                // }else{
                //     stack.offerLast(before + last * 2);
                // }
                stack.offerLast(before + Math.max(2 * last, 1));
            }
        }
        return stack.peek();
    }
}

code

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = [0]
        for v in s:
            if v == "(":
                stack.append(0)
            else:
                last = stack.pop()
                before = stack.pop()
                if last == 0:
                    stack.append(before + 1)
                else:
                    stack.append(before + last * 2)
        return stack.pop()

code

class Solution(object):
    def scoreOfParentheses(self, S):
        stack = [0] #The score of the current frame

        for x in S:
            if x == '(':
                stack.append(0)
            else:
                v = stack.pop()
                stack[-1] += max(2 * v, 1)

        return stack.pop()

code

class Solution(object):
    def scoreOfParentheses(self, S):
        ans = bal = 0
        for i, x in enumerate(S):
            if x == '(':
                bal += 1
            else:
                bal -= 1
                if S[i-1] == '(':
                    ans += 1 << bal
        return ans