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.

 

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

Difficulty: interview

Starter code:

class Solution:
    def scoreOfParentheses(self, S: str) -> int:
        

Solutions:
class Solution:
    def scoreOfParentheses(self, S: str) -> int:
        ans, val = 0, 1
        for i in range(len(S) - 1):
            if S[i: i+2] == '((': val *= 2
            if S[i: i+2] == '()': ans += val
            if S[i: i+2] == '))': val //= 2
        return ans

class Solution:
    def scoreOfParentheses(self, S: str) -> int:
        def h(i,j):
            if i > j:
                return 0
            c = 0
            ki = i
            x = 0
            for k in range(i,j+1):
                c += 1 if S[k] == '(' else -1
                if c == 0:
                    x+=max(1,2*h(ki+1,k-1))
                    ki = k+1
            return x
        return h(0,len(S)-1)