856 score of parentheses

https://leetcode.com/problems/score-of-parentheses/

class Solution {
    public int scoreOfParentheses(String s) {
        return score(s.toCharArray(), 0, s.length() - 1);
    }
    private int score(char[] array, int start, int end) {
        if (start > end) return 0;
        if (start + 1 == end) {
            return 1;
        }
        int j = start + 1;
        int leftcnt = 1;
        while (leftcnt > 0) {
            if (array[j] == ')') leftcnt--;
            if (array[j] == '(') leftcnt++;
            j++;
        }
        int left = start;
        int right = j - 1;
        if (left + 1 == right) {
            return 1 + score(array, right + 1, end);
        }
        return 2 * score(array, left + 1, right - 1) + score(array, right + 1, end);
    }
}

很娱乐的一道题

我当时为啥觉得很娱乐，明明很垃圾一道题，下面这个写法更好理解

注意判断*2情形是否合法

class Solution {
    public int scoreOfParentheses(String s) {
        return score(s.toCharArray(), 0, s.length()-1);
    }
    private int score(char[] s, int start, int end) {
        if (start >= end) {
            return 0;
        }
        if (start + 1 == end) {
            return 1;
        }
        if (s[start] == '(' && s[end] == ')') {
            int left = 0;
            int right = 0;
            boolean invalid = false;
            for (int i = start+1; i <= end-1; i++) {
                if (s[i] == '(') {
                    left++;
                } else {
                    right++;
                }
                if (left < right) {
                    invalid = true;
                    break;
                }
            }
            if (!invalid && left == right) return 2 * score(s, start+1, end-1);
        }
        int left = 0;
        int right = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                return score(s, start, i) + score(s, i+1, end);
            }
        }
        return 0;
    }
}