[Leetcode][856. Score of Parentheses] 5 Solutions: Stack, Divide and Conquer, Count of ()

By Long Luo

This article is the solution of Problem 856. Score of Parentheses.

Solution 1 Using Stack(Brute Force)

Idea

We can use Brute Force to solve this soultion.

Easy to understand, just 33 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static int scoreOfParentheses(String s) {
if (s == null || s.length() < 1) {
return 0;
}

int res = 0;
Stack<Character> stack = new Stack<>();
int len = s.length();
int idx = 0;
while (idx < len) {
while (idx < len && s.charAt(idx) == '(') {
idx++;
stack.push('(');
}

res += (int) Math.pow(2, stack.size() - 1);

while (idx < len && !stack.empty() && s.charAt(idx) == ')') {
idx++;
stack.pop();
}
}

return res;
}

Analysis

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

Solution 2 Space Optimize(Method 1)

In fact, the stack can store anything.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int scoreOfParentheses(String s) {
int res = 0;
Stack<Integer> stack = new Stack<>();
int len = s.length();
int idx = 0;
while (idx < len) {
while (s.charAt(idx) == '(') {
idx++;
stack.push(1);
}

res += (int) Math.pow(2, stack.size() - 1);

while (!stack.empty() && s.charAt(idx) == ')') {
idx++;
stack.pop();
}
}

return res;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)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 ().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int scoreOfParentheses(String s) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
for (char ch : s.toCharArray()) {
if (ch == '(') {
stack.push(0);
} else {
int subBottom = stack.pop();
int bottom = stack.pop();
stack.push(bottom + Math.max(2 * subBottom, 1));
}
}

return stack.pop();
}

Analysis

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

Solution 4 Divide and Conquer

We traverse the string SS, get several positions where the string can be split into S=P1+P2+...+PnS = P_1 + P_2 + ... + P_n, where each PiP_i is a balanced bracket string.

In this way, we can calculate separately the scores of each PiP_i. Then sum them, score(S)=score(P1)+score(P2)+...+score(Pn)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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int scoreOfParentheses_divide(String s) {
return score(s, 0, s.length());
}

public static int score(String str, int start, int end) {
int ans = 0;
int balance = 0;
for (int i = start; i < end; i++) {
if (str.charAt(i) == '(') {
balance++;
} else {
balance--;
}

if (balance == 0) {
if (i - start == 1) {
ans++;
} else {
ans += 2 * score(str, start + 1, i);
}

start = i + 1;
}
}

return ans;
}

Analysis

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

Solution 5 Count the number of ()

In fact, we can find that only ()() contributes a substantial score to the string strstr, 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 2x2^x.

It’s the best solution.

O(1)O(1) space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int scoreOfParentheses_best(String s) {
int ans = 0;
int level = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
char ch = s.charAt(i);
if (ch == '(') {
level++;
} else {
level--;
if (i > 0 && s.charAt(i - 1) == '(') {
ans += Math.pow(2, level);
}
}
}

return ans;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(1)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. 😉😃💗