856. 括号的分数

题目描述

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

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

示例 1：

输入： "()"
输出： 1

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

解法

方法一：计数

我们通过观察发现，() 是唯一贡献分数的结构，外括号只是为该结构添加了一些乘数。所以我们只需要关心 ()。

我们用 $d$ 维护当前括号的深度，对于每个 (，我们将深度加一，对于每个 )，我们将深度减一。当我们遇到 () 时，我们将 $2^d$ 加到答案中。

我们举个实际的例子，以 (()(())) 为例，我们首先找到内部两个闭合括号 ()，然后将分数加上对应的 $2^d$。实际上，我们是在计算 (()) + ((())) 的分数。

( ( ) ( ( ) ) )
  ^ ^   ^ ^

( ( ) ) + ( ( ( ) ) )
  ^ ^         ^ ^

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 是字符串的长度。

括号相关类型题：

Python3JavaC++Go

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        ans = d = 0
        for i, c in enumerate(s):
            if c == '(':
                d += 1
            else:
                d -= 1
                if s[i - 1] == '(':
                    ans += 1 << d
        return ans

class Solution {
    public int scoreOfParentheses(String s) {
        int ans = 0, d = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                ++d;
            } else {
                --d;
                if (s.charAt(i - 1) == '(') {
                    ans += 1 << d;
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int scoreOfParentheses(string s) {
        int ans = 0, d = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                ++d;
            } else {
                --d;
                if (s[i - 1] == '(') {
                    ans += 1 << d;
                }
            }
        }
        return ans;
    }
};

func scoreOfParentheses(s string) int {
    ans, d := 0, 0
    for i, c := range s {
        if c == '(' {
            d++
        } else {
            d--
            if s[i-1] == '(' {
                ans += 1 << d
            }
        }
    }
    return ans
}

856. 括号的分数

题目描述

解法

方法一：计数

评论