856. Score of Parentheses *

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Code

/**
 * 遍历
 * 记录(的个数d,就是嵌套深度
 * 当发现)的时候加上2^(d - 1)
 * 转换成加的形式
 * (()(())) -> (()) + ((()))
 * (()(()())) -> (()) + ((())) + ((()))
 */
class Solution {
    public int scoreOfParentheses(String s) {
        int ans = 0;
        int d = -1;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            d += c == '(' ? 1 : -1;

            if (s.charAt(i) == '(' && s.charAt(i + 1) == ')') {
                ans += 1 << d;
            }
        }
        return ans;
    }
}

class Solution {
    public int scoreOfParentheses(String s) {
        return helper(s, 0, s.length() - 1);
    }

    private int helper(String s, int start, int end) {
        if (end - start == 1) return 1; // ()
        int count = 0;

        for (int i = start; i < end; i++) {
            if (s.charAt(i) == '(') count++;
            if (s.charAt(i) == ')') count--;
            if (count == 0) {
                // helper("(A)(B)") = helper("(A)") + helper("(B)")
                return helper(s, start, i) + helper(s, i + 1, end);
            }
        }

        // helper("(A)") = 2 * helper("A")
        return 2 * helper(s, start + 1, end - 1);
    }
}

/**
 * ( ( ) ( ( ) ) )
 * [0, 0] after parsing (
 * [0, 0, 0] after (
 * [0, 1] after )
 * [0, 1, 0] after (
 * [0, 1, 0, 0] after (
 * [0, 1, 1] after )
 * [0, 3] after )
 * [6] after )
 */
class Solution {
    public int scoreOfParentheses(String S) {
        Stack<Integer> stack = new Stack();
        stack.push(0);

        for (char c : S.toCharArray()) {
            if (c == '(') {
                stack.push(0);
            } else {
                int v = stack.pop();
                int w = stack.pop();
                stack.push(w + Math.max(2 * v, 1));
            }
        }

        return stack.pop();
    }
}