856. Score of Parentheses

Question

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:

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

Solution

Method 1: Recursion

class Solution {
    private char[] arr;
    private int index;
    public int scoreOfParentheses(String S) {
        this.arr = S.toCharArray();
        if(arr.length == 0) return 0;
        return scoreOfParentheses(arr);
    }
    private int scoreOfParentheses(char[] arr){
        int score = 0;
        while(index < arr.length && arr[index] == '(' && arr[index + 1] == ')'){
            score += 1;
            index += 2;
        }
        if(index < arr.length){
            if(arr[index] == ')'){
                index++;
                return score;
            }else{
                index++;    //remove left bracket
                score += 2 * scoreOfParentheses(arr);
            }
        }
        if(index < arr.length) score += scoreOfParentheses(arr);
        return score;
    }
}