Leetcode 856 Score of Parentheses

发表于 |

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:

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

分析：
1.一个基础()得1分，被括起来是两倍，保证了S一定合法，且S的长度小于50，那么显然随意递归都OK

思路：
S的第一位一定是左括号，找到与之对应的右括号，然后递归即可
即形如 (s1)s2，可写成 func(s1)*2 + func(s2)

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(object):
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """
        # 设置终止条件
        if not S: return 0

        index = 0
        stack = []
        for i in range(len(S)):
            if S[i] == '(':
                stack.append(S[i])
            else:
                stack.pop()
                if not stack:
                    index = i
                    break
        # 当已经是最基本的()时，直接返回1
        if not S[1:index]:
            return 1 + self.scoreOfParentheses(S[index+1:])
        return self.scoreOfParentheses(S[1:index]) * 2 + self.scoreOfParentheses(S[index+1:])



85 / 85 test cases passed.
difficulty: medium
Runtime: 34 ms