426. Bracket Score
A decorative ribbon is encoded as a balanced string of round brackets. Its value follows three rules: an empty pair () is worth 1; two ribbons written side by side are worth the sum of their values; and a ribbon wrapped in one extra pair of brackets is worth twice the value of what it wraps.
Given the balanced string s, return the value of the whole ribbon. A recursive parse works, but the answer can also be read off in a single left-to-right sweep. The nesting depth never exceeds 12, so the result always fits in a 32-bit integer.
Example 1
- Input:
- s = "((())())()"
- Output:
- 7
- Explanation:
The first group wraps (())(), worth 2 + 1 = 3, so it is worth 6; the lone () adds 1. Total 7.
Example 2
- Input:
- s = "(()())(((())))"
- Output:
- 12
- Explanation:
(()()) wraps two pairs worth 1 + 1, so it is 4. (((()))) has three enclosing pairs around () and is worth 8. Total 12.
Constraints
2 ≤ s.length ≤ 20000s consists only of '(' and ')' and is balanced.
The nesting depth of s is at most 12.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)