题目描述
这是 LeetCode 上的 856. 括号的分数 ,难度为 中等。
Tag : 「栈」
给定一个平衡括号字符串
S
,按下述规则计算该字符串的分数:
-
得()
分。1
-
得AB
分,其中A + B
和A
是平衡括号字符串。B
-
得(A)
分,其中2 * A
是平衡括号字符串。A
示例 1:
输入: "()"
输出: 1
示例 2:
输入: "(())"
输出: 2
示例 3:
输入: "()()"
输出: 2
示例 4:
输入: "(()(()))"
输出: 6
提示:
-
是平衡括号字符串,且只含有S
和(
。)
栈
初始化将答案
0
放入栈中,从前往后处理整个
s
,当遇到
(
则存入一个占位数值
0
,遇到
)
取出栈顶元素
cur
,根据栈顶元素数值值分情况讨论:
- 栈顶元素,即当前的
的前一元素即是)
,根据(
得一分的规则可知,我们本次操作得到的分值为;()
- 栈顶元素,即当前
与其匹配的)
中间相隔了其他字符,根据(
的得分规则,此时可知得分为;(A)
将两者结合可统一为 。
由于我们每次遇到
)
时,都将最近一次操作计算出来。而再前面无论是
)
还是
(
我们都可以归结到
X()
的相邻项累加规则,将其新得分累加到栈顶元素上,其中
(
仍采用累加规则,则利用我们将
(
定义为
Java 代码:
class Solution {
public int scoreOfParentheses(String s) {
Deque<Integer> d = new ArrayDeque<>();
d.addLast(0);
for (char c : s.toCharArray()) {
if (c == '(') d.addLast(0);
else {
int cur = d.pollLast();
d.addLast(d.pollLast() + Math.max(cur * 2 , 1));
}
}
return
TypeScript 代码:
function scoreOfParentheses(s: string): number {
const stk = new Array<number>()
stk.push(0)
for (const c of s) {
if (c == '(') stk.push(0)
else {
const cur = stk.pop()
stk.push(stk.pop() + Math.max(cur * 2, 1))
}
}
return stk.pop()
}
Python 代码:
class Solution:
def scoreOfParentheses(self, s: str) -> int:
stk = [0]
for c in s:
if c == '(':
stk.append(0)
else:
cur = stk.pop()
stk.append(stk.pop() + max(cur * 2, 1))
return stk[-1]
- 时间复杂度:
- 空间复杂度:
最后
这是我们「刷穿 LeetCode」系列文章的第
No.856
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。