LeetCode 解題筆記：856. Score of Parentheses

作者：王一哲
日期：2026年10月5日


LeetCode 題目連結：856. Score of Parentheses

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, )$，保證 $s$ 之中的括號一定成對。計分的原則為：

1. 只有 $()$ 為 1 分。
2. 多個括號對相連，將這些括號對的分數相加。
3. $(A)$，其中 $A$ 為某一組括號對，分數為 $A$ 的分數乘以 2。

例如 $((()()))$，分數為 $2 \times 2 \times (1 + 1) = 4 + 4 = 8$。討論區當中有一個目前看到最厲害的寫法，假設 $n$ 為 $s$ 的長度，$depth$ 為括號對的深度，$ans$ 為答案。用一個 for 迴圈掃過 $s$，如果 $s[i]$ 是 $($，$depth += 1$；如果 $s[i]$ 是 $)$，$depth -= 1$，如果 $s[i-1]$ 是 $($，則 $ans$ 要加上這對括號的分數 $2^{depth} = 1 << depth$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.09 MB, beats 97.89%.

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        n, depth, ans = len(s), 0, 0  # 長度，括號對深度，答案
        for i in range(n):
            if s[i] == '(':  # 左括號
                depth += 1  # 深度加 1
            else:  # 右括號
                depth -= 1  # 深度減 1
                if s[i-1] == '(':  # 外面還有括號
                    ans += (1 << depth)  # 加上這對括號的分數 2**depth
        return ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 7.69 MB, beats 99.92%.

class Solution {
public:
    int scoreOfParentheses(string s) {
        int n = (int)s.size(), depth = 0, ans = 0;  // 長度，括號對深度，答案
        for(int i = 0; i < n; i++) {
            if (s[i] == '(') {  // 左括號
                depth++;  // 深度加 1
            } else {  // 右括號
                depth--;  // 深度減 1
                if (s[i-1] == '(') {  // 外面還有括號
                    ans += (1 << depth);  // 加上這對括號的分數 2**depth
                }
            }
        }
        return ans;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.63 MB, beats 36.36%.

int scoreOfParentheses(char* s) {
    int n = strlen(s), depth = 0, ans = 0;  // 長度，括號對深度，答案
    for(int i = 0; i < n; i++) {
        if (s[i] == '(') {  // 左括號
            depth++;  // 深度加 1
        } else {  // 右括號
            depth--;  // 深度減 1
            if (s[i-1] == '(') {  // 外面還有括號
                ans += (1 << depth);  // 加上這對括號的分數 2**depth
            }
        }
    }
    return ans;
}