動機

用stack去計分數，另外solution的解法很神

Problem

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

Example 4:

Input: s = "(()(()))"Output: 6

 

Constraints:

  • 2 <= s.length <= 50
  • s consists of only '(' and ')'.
  • s is a balanced parentheses string.

Sol

stack放左括號與當前分數，只要遇到分數就是乘2

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stk = []
        for c in s:
            if c == "(":
                stk += c,
            elif stk[-1] == "(":
                stk.pop()
                stk += 1,
            else:
                ret = 0
                while stk and stk[-1] != "(":
                    ret += stk.pop()
                stk[-1] = ret*2
        return sum(stk, 0)

trace括號的深度，在有()時就直接加2^dep

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