[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 $2$, as every core (a substring $()$, with score $1$ ) will have it’s score multiplied by $2$ for each exterior set of parentheses that contains that core.

Since $s$ is a balanced parentheses string, we can replace $()$ by $1$, then the result is still a balanced parentheses string.

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

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

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