Question

856. 括号的分数

English Version

题目描述

给定一个平衡括号字符串 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

解法

方法一：计数

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

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

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

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

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

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

括号相关类型题：

• 678. 有效的括号字符串
• 1021. 删除最外层的括号
• 1096. 花括号展开 II
• 1249. 移除无效的括号
• 1541. 平衡括号字符串的最少插入次数
• 2116. 判断一个括号字符串是否有效

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
}