856. Score of Parentheses

1. Description

Compute the score of a balanced string s made of parentheses using these rules:

• An innermost pair “()” contributes 1.
• Joining two balanced strings adds their individual scores.
• Wrapping a nonempty balanced string in another pair of parentheses doubles its score.

2. Example

Example 1

Input: s = “()”
Output: 1

Example 2

Input: s = “(())”
Output: 2

Example 3

Input: s = “()()”
Output: 2

3. Constraints

• 2 <= s.length <= 50
• Each character of s is either ‘(’ or ‘)’.
• The input is guaranteed to be balanced.

4. Solutions

Counting Depth

n = str.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int scoreOfParentheses(const string &str) {
        int depth = 0, score = 0;
        for (int i = 0, n = str.size(); i < n; ++i) {
            if (str[i] == '(') {
                ++depth;
            } else {
                --depth;
                if (str[i - 1] == '(') {
                    score += 1 << depth;
                }
            }
        }

        return score;
    }
};