平衡括号(二)——判断平衡括号扩展

LeetCode_856_ScoreOfParentheses

题目分析：

利用上题提到的平衡括号特性，判断当前串是 AB 型 还是 (A)型即可。
从第一个字符开始数子串，第一个"("个数等于")"个数的子串
即是一个完整的平衡括号串。
递归妙不可言

解法：

public static int scoreOfParentheses(String S) {
    if(S.equals("()"))
        return 1;
    int left = 0, right = 0;
    int i = 0;
    for (; i < S.length(); i++) {
        if('(' == S.charAt(i))
            left++;
        else right++;
        if(left <= right)
            break;
    }
    if(i != S.length() - 1)//如果i不是S.length() - 1 i是从0开始的有效串的最后一位
        return scoreOfParentheses(S.substring(0, i + 1)) + scoreOfParentheses(S.substring(i + 1, S.length()));
    else
        return 2 * scoreOfParentheses(S.substring(1, S.length() - 1));
}