856. Score of Parentheses
https://leetcode.com/problems/score-of-parentheses/
Given a balanced parentheses string S, compute the score of the string based on the following rule:
()has score 1ABhas scoreA + B, where A and B are balanced parentheses strings.(A)has score2 * A, where A is a balanced parentheses string.
Example 1:
Input: "()" Output: 1
Example 2:
Input: "(())" Output: 2
Example 3:
Input: "()()" Output: 2
Example 4:
Input: "(()(()))" Output: 6
Note:
Sis a balanced parentheses string, containing only(and).2 <= S.length <= 50
----
Intuition
Only () contribute to final score
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int scoreOfParentheses(String S) { | |
| int ans = 0; | |
| int level = 0; | |
| for (int i = 0; i < S.length(); i++) { | |
| if (S.charAt(i) == '(') { | |
| level++; | |
| } else { | |
| level--; | |
| // Only thing that adds value is () .. = 2 ^ level | |
| if (S.charAt(i - 1) == '(') { | |
| ans += 1 << level; | |
| } | |
| } | |
| } | |
| return ans; | |
| } | |
| } |
