856. Score of Parentheses

Description

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.

Constraints

• S is a balanced parentheses string, containing only ( and ).

• 2 <= S.length <= 50

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: "()"

Output: 1

Example 2

Input: "(())"

Output: 2

Example 3

Input: "()()"

Output: 2

Example 4

Input: "(()(()))"

Output: 6

Solutions

Solution 1

/**
 * Time complexity : O(N), where N is the length of S.
 * Space complexity : O(N), the size of the stack.
 */

class Solution {
    public int scoreOfParentheses(String S) {
        if(S == null || S.length() == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack();
        int score = 0;
        for(char ch: S.toCharArray()) {
            if(ch == '(') {
                stack.push(score);
                score = 0;
            } else {
                score = stack.pop() + Math.max(score*2, 1);
            }
        }
        return score;
    }
}

Solution 2

/**
 * Time complexity : O(N), where N is the length of S.
 * Space complexity : O(1)
 */

class Solution {

    public int scoreOfParentheses(String S) {
        int ans = 0, bal = 0;
        for (int i = 0; i < S.length(); ++i) {
            if (S.charAt(i) == '(') {
                bal++;
            } else {
                bal--;
                if (S.charAt(i-1) == '(')
                    ans += 1 << bal;
            }
        }

        return ans;
    }
}

Follow up