2021-11-26：() 分值为2， (()) 分值为3， ((())) 分值为4， 也就是说，每包裹一层，分数就是里面的分值+1。 ()() 分值为2 * 2， (())() 分值为3 * 2。 也就是说，每连接一段，分数就是各部分相乘，以下是一个结合起来的例子， (()())()(()) -> (2 * 2 + 1) * 2 * 3 -> 30。 给定一个括号字符串str，已知str一定是正确的括号结合，不会有违规嵌套， 返回分数。 来自美团。

答案2021-11-26：

递归。f(i)，遇到左括号，调用f(i+1)；遇到右括号，f(i)返回。 f(i)的返回值有两个，一个是分数，一个是序号。 时间复杂度：O((N)。 空间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    s := "(()())()(())"
    ret := sores(s)
    fmt.Println(ret)
}

func sores(s string) int {
    return compute(s, 0)[0]
}

// s[i.....] 遇到 ')' 或者 终止位置  停！
// 返回值：int[]  长度就是2
// 0 ：分数是多少
// 1 : 来到了什么位置停的！
func compute(s string, i int) []int {
    if s[i] == ')' {
        return []int{1, i}
    }
    ans := 1
    for i < len(s) && s[i] != ')' {
        info := compute(s, i+1)
        ans *= info[0] + 1
        i = info[1] + 1
    }
    return []int{ans, i}
}

执行结果如下： 图片

左神java代码