By Long Luo

# Solution 1 Using Stack(Brute Force)

## Idea

We can use Brute Force to solve this soultion.

Easy to understand, just $3$ steps:

1. build a stack
2. If you encounter (, add it to the stack
3. If you encounter ), calculate the score and pop stack.

So Easy.

## Analysis

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n)$

# Solution 2 Space Optimize(Method 1)

In fact, the stack can store anything.

## Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

# Solution 3 Stack Better

Method 2 is staill redundant, we can use the stack to store the score instead.

To calculate the score, we should be careful when meet ().

## Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

# Solution 4 Divide and Conquer

We traverse the string $S$, get several positions where the string can be split into $S = P_1 + P_2 + ... + P_n$, where each $P_i$ is a balanced bracket string.

In this way, we can calculate separately the scores of each $P_i$. Then sum them, $score(S) = score(P_1) + score(P_2) + ... + score(P_n)$.

For an unsplittable balanced bracket string, if it is (), then it will get 1 point, otherwise it must have a pair of left and right brackets in the outermost layer. You can remove the pair of brackets and continue to split, and then you will get Multiply the fraction by 2.

## Analysis

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n)$

# Solution 5 Count the number of ()

In fact, we can find that only $()$ contributes a substantial score to the string $str$, the other parentheses just multiply the score by two or add it up.

Therefore, we can find the depth x corresponding to each (), then the answer is the cumulative sum of $2^x$.

It’s the best solution.

$O(1)$ space.

## Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗