java - 递归 - 括号分数

Question

我正在尝试使用递归解决括号分数的 leet 代码问题。

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

我想明确地使用递归。对于这种预期答案为 3 而我返回 4 的情况，它会失败。 (())()如何使用递归解决这个问题？

    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

我会这样做，使用 int[] 来跟踪字符串的进展。

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;
}

Answer 2

这是法官接受的没有循环或全局引用的递归。它不仅返回分数，还返回一个元组[score, index_after_parenthetical].

JavaScript 代码：

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));