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 score1
.AB
has scoreA + B
, whereA
andB
are balanced parentheses strings.(A)
has score2 * A
, whereA
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
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|