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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

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)