[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 , as every core (a substring , with score ) will have it’s score multiplied by for each exterior set of parentheses that contains that core.
Since is a balanced parentheses string, we can replace by , then the result is still a balanced parentheses string.
For example, will become . The sum is .
As a result, let , we can make when we meet , when we meet , and add when we meet .
1 | class Solution { |
Analysis
- Time Complexity: .
- Space Complexity: .
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. 😉😃💗