856. Score of Parentheses (Python)

Related Topic

Stack.

Description

Given a balanced parentheses string S, compute the score of the string 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.

Sample I/O

Example 1

Input: "()"
Output: 1

Example 2

Input: "(())"
Output: 2

Example 3

Input: "()()"
Output: 2

Example 4

Input: "(()(()))"
Output: 6

Note

1. S is a balanced parentheses string, containing only ( and ).
2. 2 <= S.length <= 50

Methodology

This is typical stack question. We create a stack to store temp value. The value can be either ‘(‘ or number. We iterate the string. If we meet ‘(‘, then append the ‘(‘ to the stack. If we meet others, then we go into the stack and check the top element of the stack. If the top element is ‘(‘ then append 1 to the stack. Otherwise, we will go backward and sum all number until the top element of stack is ‘(‘, we append 2*sum to the stack and continue.

def scoreOfParentheses(self, S: str) -> int:
        stack = []
        for s in S:
            if s == '(':
                stack.append(s)
            else:
                m = stack.pop()
                if m == '(': stack.append(1)
                else:
                    tmp = 0
                    while m != '(':
                        tmp+=m
                        m = stack.pop()
                    stack.append(2*tmp)
        return sum(stack)

BigO

Iterate the string will cost O(n) and iterate stack will be totol O(n/2) so the time complexity is O(n)