8 用栈&搜索解决括号问题

856. 括号的分数

前言

「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 8 篇题解，更多题解关注 Somnia1337@力扣。

题目描述

难度：🟡中等

标签：#栈字符串

给定一个平衡括号字符串 s，按下述规则计算该字符串的分数：

() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。

输入："(()(()))"
输出：6
解释：内层的 "()" 1 分、"(())" 1*2=2 分，最终 (1+2)*2=6 分

解题思路

外挂：Python 调库

调库作如下替换：

”)(” 换为 ”)+(”
”()” 换为 “1”
”(” 换为 “2*(”

这样，”(()(()))” 变为 “2*(1+2*(1))“，再调用 eval() 计算中缀表达式的值。

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        return eval(s.replace(")(", ")+(").replace("()", "1").replace("(", "2*("))

“答得不错，今天的面试就到这里吧！”

方法 1：DFS

思路与图片来源 HongKy@力扣。

括号之间有着明显的层级关系，可以将之视为树状结构：

当一个结点没有子结点的时候，那么这个结点的值为 1
否则，为所有子结点之和 * 2

用 c == ')' 判断结点的开始，同样判断是否有子结点。

class Solution {
    private int it = 0;
	
    public int scoreOfParentheses(String s) {
        int ans = 0;
        while (it < s.length() && s.charAt(it) == '(') {
            it++;
            if (s.charAt(it) == ')') ans++; // 没有子结点
            else ans += scoreOfParentheses(s) * 2; // 有子结点
            it++;
        }
        return ans;
    }
}

方法 2：栈

定义空串的分数为 0，遍历：

遇到 ’(’ 时，压入 0，作为暂时的分数。
遇到 ’)’ 时，弹出的分数为当前括号对之间的分数，将其乘 2，与 1 取较大者，加上再次弹出的分数

以 ”(()(()))” 为例，展示这个过程：

i  c  stk
-1    [0
0  (  [0,0
1  (  [0,0,0
2  )  [0,1
3  (  [0,1,0
4  (  [0,1,0,0
5  )  [0,1,1
6  )  [0,3
7  )  [6

class Solution {
    public int scoreOfParentheses(String s) {
        Deque<Integer> stk = new ArrayDeque<>();
        stk.push(0); // 初始时压入 0
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') stk.push(0); // 压栈
            else stk.push(Math.max(2 * stk.pop(), 1) + stk.pop()); // 更新栈顶
        }
        return stk.peek(); // 栈顶元素即为答案
    }
}

方法 3：加权和

从根源上，分数全部来源于原子括号对 ”()“，对深度为 d 的原子，它对最终分数的贡献为 $2^{d}$ 。遍历时，遇到 ’(’ 将 d 加 1、遇到 ’)’ 将 d 减 1，并在匹配到原子时将 1 << d 累加到答案。

class Solution {
    public int scoreOfParentheses(String s) {
        int n = s.length(), d = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            d += (s.charAt(i) == '(' ? 1 : -1); // 更新深度
            if (s.charAt(i) == ')' && s.charAt(i - 1) == '(') ans += 1 << d; // 匹配到原子, 累加答案
        }
        return ans;
    }
}

最后

更多系列「外源推文」&「生活分享」关注公众号：

🥑 EmberNecro

Explorer