LeetCode #856 Score of Parentheses

Posted on | Post modified | In , , , , , ,

Problem

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.

Examples

1
2
Input: "()"
Output: 1
1
2
Input: "(())"
Output: 2
1
2
Input: "()()"
Output: 2
1
2
Input: "(()(()))"
Output: 6

Solution

Method: Stack

Time Complexity: O(n)

Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """
        ret = ['(']

        for idx in range(1, len(S)):
            if S[idx] == ')':
                if ret[-1] == '(':
                    ret.pop()
                    if ret:
                        if ret[-1] == '(':
                            ret.append(1)
                        else:
                            val = ret.pop()
                            ret.append(val + 1)
                    else:
                        ret.append(1)
                else:
                    val = ret.pop()
                    ret.pop()
                    if not ret or ret[-1] == '(':
                        ret.append(2 * val)
                    else:
                        pre_val = ret.pop()
                        ret.append(2 * val + pre_val)
            else:
                ret.append('(')

        return ret[0]

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """
        ret = []

        for s in S:
            if not ret or s == '(':
                ret.append(s)
            else:
                if ret[-1] == '(':
                    ret.pop()
                    if not ret or ret[-1] == '(':
                        ret.append(1)
                    else:
                        val = ret.pop()
                        ret.append(val + 1)
                else:
                    val = ret.pop()
                    ret.pop()
                    if not ret or ret[-1] == '(':
                        ret.append(2 * val)
                    else:
                        pre_val = ret.pop()
                        ret.append(2 * val + pre_val)

        return ret[0]