Medium

题目描述

给定一个平衡括号字符串 s，返回该字符串的分数。

平衡括号字符串的分数基于以下规则：

  • "()" 的分数为 1
  • AB 的分数为 A + B，其中 A 和 B 是平衡括号字符串
  • (A) 的分数为 2 * A，其中 A 是平衡括号字符串

示例 1：

输入：s = "()"
输出：1

示例 2：

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

示例 3：

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

提示：

  • 2 <= s.length <= 50
  • s 仅由 '(' 和 ')' 组成
  • s 是平衡括号字符串

解题思路

这道题可以用多种方法解决，主要思路有栈和数学计算两种。

方法一：栈模拟 使用栈来模拟括号匹配过程。当遇到左括号时，将当前分数入栈并重置；当遇到右括号时，计算当前层的分数。如果当前分数为0（表示是空的括号对），则得分为1，否则得分为当前分数的2倍，然后加到栈顶元素上。

方法二：深度计算 观察规律可发现，每个 () 对的贡献与其嵌套深度有关。深度为 d 的 () 对贡献 2^d 分。我们可以遍历字符串，维护当前深度，当遇到 () 时累加 2^深度。

方法三：递归分治 根据题目规则，可以递归地计算分数：找到匹配的括号对，如果内部为空则返回1，否则返回2倍的内部分数，然后继续处理剩余部分。

这里给出最优的深度计算解法，时间复杂度最低且代码简洁。

代码实现

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

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        score = 0
        depth = 0
        for i in range(len(s)):
            if s[i] == '(':
                depth += 1
            else:
                depth -= 1
                if s[i-1] == '(':
                    score += 1 << depth
        return score

public class Solution {
    public int ScoreOfParentheses(string s) {
        int score = 0, depth = 0;
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                depth++;
            } else {
                depth--;
                if (s[i-1] == '(') {
                    score += 1 << depth;
                }
            }
        }
        return score;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var scoreOfParentheses = function(s) {
    let score = 0, depth = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)