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

Example 3

Example 4

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

Follow up