856.Score of Parentheses
Given a balanced parentheses string S, compute the score of the string based on the following rule:
()has score 1ABhas scoreA + B, where A and B are balanced parentheses strings.(A)has score2 * 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("(()())"));
}
}
