Score of Parentheses-LeetCode#856

856.Score of Parentheses

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

思路:递归,找只有 ‘(‘ 与 ‘)‘的时候返回1,如果有嵌套*2,平行相加

public class ScoreOfParentheses {
    public int scoreOfParentheses(String S) {
        return recursion(S.toCharArray(), 0, S.length() - 1);
    }
    public int recursion(char[] str, int s, int e) {
        if (e - s == 1) return 1;
        int b = 0;
        for (int i = s; i < e; i++) {
            if (str[i] == '(') b++;
            if (str[i] == ')') b--;
            if (b == 0) return recursion(str, s, i) + recursion(str, i + 1, e);
        }
        return 2 * recursion(str, s + 1, e - 1);
    }
    public static void main(String[] args) {
        ScoreOfParentheses scoreOfParentheses = new ScoreOfParentheses();
        System.out.println(scoreOfParentheses.scoreOfParentheses("(()())"));
    }
}
文章已创建 108

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部