题目连接：点击跳转
思路
方法一、分治 + DFS
这题的意思让你区分AB以及(A)的形式算出，计算出整个该字符串的分数。怎么区分呢，用分治的思想，我们需要先找到平衡的字符串，我们将左括号算做+1，右括号算做-1，通过遍历字符串算分数.
- 如果sum == 0，表示从0开始到当前的位置是一个平衡字符串数组，我们需要判断(A)还是AB形式的。
。当前的位置是字符串的结尾，他一定是(A)的形式，去掉首位括号，继续进行分治，直到()的形式。
。当前的位置不是字符串结尾，他一定是AB的形式，我们从当前位置为分割点s[0:i]为平衡字符串A，s[I + 1: n - 1]为平衡字符串B，两者分别进行分治，直到()的形式。
。如果s的长度为2，他一定是()的形式，则直接返回1即可。
代码示例
func scoreOfParentheses(s string) int { if len(s) == 2 { return 1 } for i, sum := 0, 0; i < len(s); i++ { if s[i] == '(' { sum++ }else{ sum-- if sum == 0{ if i == len(s) - 1{ return 2 * scoreOfParentheses(s[1:i]) } return scoreOfParentheses(s[:i + 1]) + scoreOfParentheses(s[i + 1:]) } } } return 1 }
复杂度分析
- 时间复杂度：O(N)，其中N表示字符串的长度，分治会遍历整个字符串需要O(N)的时间。
- 空间复杂度：O(1)，不需要额外申请空间。
