原文链接: https://leetcode-cn.com/problems/score-of-parentheses

英文原文

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.

中文题目

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

• () 得 1 分。
• AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
• (A) 得 2 * A 分，其中 A 是平衡括号字符串。

 

示例 1：

输入： "()"
输出： 1

示例 2：

输入： "(())"
输出： 2

示例 3：

输入： "()()"
输出： 2

示例 4：

输入： "(()(()))"
输出： 6

 

提示：

1. S 是平衡括号字符串，且只含有 ( 和 ) 。
2. 2 <= S.length <= 50

通过代码

官方题解

方法一：分治

对于一个字符串 S，我们将左括号 ( 记为 1，右括号记为 -1，如果 S 的某一个非空前缀对应的和为 0，那么这个前缀就是一个平衡括号字符串。我们遍历字符串 S，得到若干个前缀和为 0 的位置，就可以将字符串拆分为 S = P_1 + P_2 + ... + P_n，其中每一个 P_i 都是一个平衡括号字符串。这样我们就可以分别计算每一个 P_i 的分数再相加，即 score(S) = score(P_1) + score(P_2) + ... + score(P_n)。

对于一个不可拆分的平衡括号字符串，如果它为 ()，那么就得 1 分，否则它的最外层一定有一对左右括号，可以将这对括号去除后继续进行拆分，再将得到的分数乘 2。

[sol1]
class Solution {

    public int scoreOfParentheses(String S) {
        return F(S, 0, S.length());
    }

    public int F(String S, int i, int j) {
        //Score of balanced string S[i:j]
        int ans = 0, bal = 0;

        // Split string into primitives
        for (int k = i; k < j; ++k) {
            bal += S.charAt(k) == '(' ? 1 : -1;
            if (bal == 0) {
                if (k - i == 1) ans++;
                else ans += 2 * F(S, i+1, k);
                i = k+1;
            }
        }

        return ans;
    }
}

[sol1]
class Solution(object):
    def scoreOfParentheses(self, S):
        def F(i, j):
            #Score of balanced string S[i:j]
            ans = bal = 0

            #Split string into primitives
            for k in xrange(i, j):
                bal += 1 if S[k] == '(' else -1
                if bal == 0:
                    if k - i == 1:
                        ans += 1
                    else:
                        ans += 2 * F(i+1, k)
                    i = k+1

            return ans

        return F(0, len(S))

复杂度分析

• 时间复杂度：$O(N^2)$，其中 $N$ 是字符串 S 的长度，在最坏的情况下，字符串 S 为 (((((((....)))))))，它需要拆分 $O(N)$ 次，每次遍历字符串的时间复杂度也为 $O(N)$。

• 空间复杂度：$O(N)$。

方法二：栈

字符串 S 中的每一个位置都有一个“深度”，即该位置外侧嵌套的括号数目。例如，字符串 (()(.())) 中的 . 的深度为 2，因为它外侧嵌套了 2 层括号：(__(.__))。

我们用一个栈来维护当前所在的深度，以及每一层深度的得分。当我们遇到一个左括号 ( 时，我们将深度加一，并且新的深度的得分置为 0。当我们遇到一个右括号 ) 时，我们将当前深度的得分乘二并加到上一层的深度。这里有一种例外情况，如果遇到的是 ()，那么只将得分加一。

下面给出了字符串 (()(())) 每次对应的栈的情况：

• [0, 0] (
• [0, 0, 0] ((
• [0, 1] (()
• [0, 1, 0] (()(
• [0, 1, 0, 0] (()((
• [0, 1, 1] (()(()
• [0, 3] (()(())
• [6] (()(()))

[sol2]
public int scoreOfParentheses(String S) {
    Stack<Integer> stack = new Stack();
    stack.push(0); // The score of the current frame

    for (char c: S.toCharArray()) {
        if (c == '(')
            stack.push(0);
        else {
            int v = stack.pop();
            int w = stack.pop();
            stack.push(w + Math.max(2 * v, 1));
        }
    }

    return stack.pop();
}

[sol2]
class Solution(object):
    def scoreOfParentheses(self, S):
        stack = [0] #The score of the current frame

        for x in S:
            if x == '(':
                stack.append(0)
            else:
                v = stack.pop()
                stack[-1] += max(2 * v, 1)

        return stack.pop()

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是字符串 S 的长度。

• 空间复杂度：$O(N)$，为栈的大小。

方法三：统计核心的数目

事实上，我们可以发现，只有 () 会对字符串 S 贡献实质的分数，其它的括号只会将分数乘二或者将分数累加。因此，我们可以找到每一个 () 对应的深度 x，那么答案就是 2^x 的累加和。

[sol3]
class Solution {

    public int scoreOfParentheses(String S) {
        int ans = 0, bal = 0;
        for (int i = 0; i < S.length(); ++i) {
            if (S.charAt(i) == '(') {
                bal++;
            } else {
                bal--;
                if (S.charAt(i-1) == '(')
                    ans += 1 << bal;
            }
        }

        return ans;
    }
}

[sol3]
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

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是字符串 S 的长度。

• 空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
16936	26961	62.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言