() 分值为2,
(()) 分值为3,
((())) 分值为4,
也就是说,每包裹一层,分数就是里面的分值+1。
()() 分值为2 * 2,
(())() 分值为3 * 2。
也就是说,每连接一段,分数就是各部分相乘,以下是一个结合起来的例子,
(()())()(()) -> (2 * 2 + 1) * 2 * 3 -> 30。
给定一个括号字符串str,已知str一定是正确的括号结合,不会有违规嵌套,
返回分数。
递归。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}
}
执行结果如下: