0856. Score of Parentheses (M)

题目

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

Note:

1. S is a balanced parentheses string, containing only ( and ).
2. 2 <= S.length <= 50

题意

“()”为1分，在其外部每套上一对括号分数翻倍，求一个字符串代表的分数。

思路

分治：对于一个合法字符串，如果我们能把它分为(…)(…)的形式，那么只要计算两个子串的分数再相加即可；如果不能分成两部分，则一定是(……)的形式，那么我们只要计算内部串的分数再将其乘以2即可。

计算：注意到所有分数的来源是”()”代表的1分，我们可以从左到右遍历字符串，记录剩余未匹配的左括号的个数left，如果当前字符是’)’，且前一个字符为’(‘，那么我们获得1分，而它对应的最终得到的分数是1<<left，即在这一对括号的左侧每有一个尚未匹配的左括号，都会将这对括号代表的最终分数翻倍。

代码实现

Java

分治

class Solution {
    public int scoreOfParentheses(String S) {
        if (S.length() == 2) return 1;
        int left = 1;
        int i = 1;
        while (left > 0) {
            left += S.charAt(i++) == '(' ? 1 : -1;
        }
        if (i == S.length()) {
            return 2 * scoreOfParentheses(S.substring(1, i - 1));
        } else {
            return scoreOfParentheses(S.substring(0, i)) + scoreOfParentheses(S.substring(i));
        }
    }
}

计算

class Solution {
    public int scoreOfParentheses(String S) {
        int score = 0;
        int left = 0;
        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == '(') {
                left++;
            } else {
                left--;
                if (S.charAt(i - 1) =='(') score += 1 << left;
            }
        }
        return score;
    }
}