README_EN.md

comments	difficulty	edit_url	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/0800-0899/0856.Score%20of%20Parentheses/README_EN.md	Stack String

856. Score of Parentheses

中文文档

Description

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule:

• "()" has score 1.
• AB has score A + B, where A and B are balanced parentheses strings.
• (A) has score 2 * A, where A is a balanced parentheses string.

 

Example 1:

Input: s = "()"
Output: 1

Example 2:

Input: s = "(())"
Output: 2

Example 3:

Input: s = "()()"
Output: 2

 

Constraints:

• 2 <= s.length <= 50
• s consists of only '(' and ')'.
• s is a balanced parentheses string.

Solutions

Solution 1: Counting

By observing, we find that () is the only structure that contributes to the score, and the outer parentheses just add some multipliers to this structure. So, we only need to focus on ().

We use $d$ to maintain the current depth of parentheses. For each (, we increase the depth by one, and for each ), we decrease the depth by one. When we encounter (), we add $2^d$ to the answer.

Let's take (()(())) as an example. We first find the two closed parentheses () inside, and then add the corresponding $2^d$ to the score. In fact, we are calculating the score of (()) + ((())).

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

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

The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the string.

Related problems about parentheses:

• 678. Valid Parenthesis String
• 1021. Remove Outermost Parentheses
• 1096. Brace Expansion II
• 1249. Minimum Remove to Make Valid Parentheses
• 1541. Minimum Insertions to Balance a Parentheses String
• 2116. Check if a Parentheses String Can Be Valid

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}