Leetcode 856. Score of Parentheses

Given a balanced parentheses string S, compute the score of the string based on the following rule:

• () has score 1
• AB has score A + B, where A and B are balanced parentheses strings.
• (A) has score 2 * 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:

1. S is a balanced parentheses string, containing only ( and ).
2. 2 <= S.length <= 50

Code (Java):

?

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 27 28 29 30 31 32 33 34 35 36

class Solution {     public int scoreOfParentheses(String S) {         if (S == null || S.length() == 0) {             return 0;         }           int ans = 0;                Stack<Integer> stack = new Stack<>();                   for (char c : S.toCharArray()) {             if (c == '(') {                 stack.push(-1);             } else {                 int curr = 0;                 while (stack.peek() != -1) {                     curr += stack.pop();                 }                                   stack.pop(); // '('                                   if (curr == 0) {                     curr = 1;                 } else {                     curr *= 2;                 }                 stack.push(curr);             }         }                   while (!stack.isEmpty()) {             ans += stack.pop();         }                   return ans;     } }

Solution 2: O(1) space
We use a counter to maintain the number of open left parenthesis.
If the current char is '(', counter++
If the current is ')', counter--
If the current is "()" we know the current number of open left parentheiss outside,
then score += 1 << counter
The key observation for the solution is score of (()()()) = (()) + (()) + (()), so we can calculate
the score and sum it up.
Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution {     public int scoreOfParentheses(String S) {         int left = 0;         int score = 0;                   for (int i = 0; i < S.length(); i++) {             char c = S.charAt(i);             if (c == '(') {                 left++;             } else {                 left--;                 if (S.charAt(i - 1) == '(') {                     score += 1 << left;                 }             }         }                   return score;     } }