[LeetCode][856. Score of Parentheses] The Tricky and Clean Solution: Replace Core by 1

By Long Luo

This article is the solution The Tricky and Clean Solution: Replace Core by 1 of Problem 856. Score of Parentheses.

There are many approaches about this problem, like Stack, Divide and Conquer, Count Cores and so on. Here shows a Tricky and Clean solution.

Intuition

The sum will be a sum of powers of 22, as every core (a substring ()(), with score 11 ) will have it’s score multiplied by 22 for each exterior set of parentheses that contains that core.

Since ss is a balanced parentheses string, we can replace ()() by 11, then the result is still a balanced parentheses string.

For example, (()())(()()) will become (1(1))(1(1)). The sum is (1+1×2)×2=1×2+1×2×2=6(1 + 1 \times 2) \times 2 = 1 \times 2 + 1 \times 2 \times 2 = 6.

As a result, let base=1base = 1, we can make base=base×2base = base \times 2 when we meet ((, base=base÷2base = base \div 2 when we meet ((, and add 11 when we meet 11.

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
class Solution {
public int scoreOfParentheses(String s) {
s = s.replace("()", "1");

int ans = 0;
int base = 1;

for (char ch : s.toCharArray()) {
switch (ch) {
case '(':
base *= 2;
break;

case ')':
base /= 2;
break;

default:
ans += base;
break;
}
}

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. 😉😃💗