Recursion - Score Of Parentheses

Question

I am trying to solve the leet code problem of Score of Parentheses using recursion.

https://leetcode.com/problems/score-of-parentheses/

I want to explicitly use recursion. It fails for cases like this (())() where expected answer is 3 and i return 4. How to solve this using recursion?

    public int scoreOfParentheses(String S) {
        return paran(S, 0);
    }

    int paran(String s, int c){
        // base case exit
        if(c >= s.length())
            return 0;
        if(s.charAt(c) == '(' && s.charAt(c + 1) == ')'){
            return 1 + paran(s, c + 2);
        }
        else if(s.charAt(c) == '('){
            return 2 * paran(s, c + 1);
        }
        return paran(s , c + 1);
    }

Answer 1

Here's a recursion without loops or global references that's accepted by the judge. Rather than just the score, it returns a tuple, [score, index_after_parenthetical].

JavaScript code:

function f(s, i=0){
  if (i == s.length)
    return [0, i];
    
  if (s[i] == '('){
    const [inner, j] = f(s, i + 1);  
    const [after, k] = f(s, j);

    return [2 * (inner || 0.5) + after, k];
  }

  return [0, i + 1];
}

var strs = ["(())", "(()(()))"];

for (const s of strs)
  console.log(s + ': ' + f(s));

Answer 2

I would do it in this way, using a int[] to keep track of the advancement over the string.

static int score(String str, int[] i) {
    int score=0;
    while (i[0]<str.length()) {
        char c=str.charAt(i[0]++);
        if (c=='(') {
            int val=score(str,i);
            if (val==0) {
                score++;
            } else {
                score+=2*val;
            }
        } else {
            return score;
        }
    }
    return score;
}