【2022-10-09每日一题】856. 括号的分数[Medium]
2022-10-09
2分钟阅读时长
2022-10-09每日一题：856. 括号的分数
难度：Medium
标签：栈 、 字符串
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
()得 1 分。AB得A + B分，其中 A 和 B 是平衡括号字符串。(A)得2 * A分，其中 A 是平衡括号字符串。
示例 1：
输入： "()" 输出： 1
示例 2：
输入： "(())" 输出： 2
示例 3：
输入： "()()" 输出： 2
示例 4：
输入： "(()(()))" 输出： 6
提示：
S是平衡括号字符串，且只含有(和)。2 <= S.length <= 50
方法一：栈
核心思想
把平衡字符串 s 看作是一个空字符串加上 s 本身，并且定义空字符串的分数为 0。使用栈 st 记录平衡字符串的分数，在开始之前要压入分数 0，表示空字符串的分数。
在遍历字符串 s 的过程中：
遇到左括号，那么我们需要计算该左括号内部的子平衡括号字符串A 的分数，我们也要先压入分数 0，表示 A 前面的空字符串的分数。
遇到右括号，说明该右括号内部的子平衡括号字符串 A 的分数已经计算出来了，我们将它弹出栈，并保存到变量 v 中。如果 v = 0，那么说明子平衡括号字符串 A 是空串，(A)的分数为 1，否则 (A) 的分数为 2v，然后将 (A) 的分数加到栈顶元素上。
遍历结束后，栈顶元素保存的就是 s 的分数。
代码
func scoreOfParentheses(s string) int {
st := []int{0}
for _, c := range s {
if c == '(' { // 遇到左括号
st = append(st, 0)
} else { // 遇到又括号
v := st[len(st)-1]
st = st[:len(st)-1]
// 巧妙处理：如果 v = 0，那么说明子平衡括号字符串 A 是空串，(A)的分数为 1，
// 否则 (A) 的分数为 2v，然后将 (A) 的分数加到栈顶元素上。
st[len(st)-1] += max(2*v, 1)
}
}
return st[0]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串的长度。
- 空间复杂度：O(n)。栈需要 O(n)的空间。
方法二：计算最终分数和
根据题意，s 的分数与 1 分的 () 有关。对于每个 ()，它的最终分数与它所处的深度有关，如果深度为 bal，那么它的最终分数为 2^bal。我们统计所有 () 的最终分数和即可。
func scoreOfParentheses(s string) (ans int) {
bal := 0
for i, c := range s {
if c == '(' {
bal++
} else {
bal--
if s[i-1] == '(' {
ans += 1 << bal
}
}
}
return ans
}
复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串的长度。
- 空间复杂度：O(1)。
方法三：分治
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func scoreOfParentheses(s string) int {
n := len(s)
// s 的长度为 2 时，分数为 1
if n == 2 {
return 1
}
for i, bal := 0, 0; ; i++ {
if s[i] == '(' {
// 左括号记为 1
bal++
} else {
// 右括号记为 -1
bal--
// 前缀是一个平衡括号字符串
if bal == 0 {
// 前缀长度等于 s 的长度，s 可以分解为 (A) 的形式
if i == n - 1 {
return 2 * scoreOfParentheses(s[1:n-1])
}
// s 可以分解为 A+B 的形式
return scoreOfParentheses(s[:i+1]) + scoreOfParentheses(s[i+1:])
}
}
}
}
复杂度分析
- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)