【python-leetcode856-子集】括号的分数

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

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

示例 1：

输入： "()"
输出： 1
示例 2：

输入： "(())"
输出： 2
示例?3：

输入： "()()"
输出： 2
示例?4：

输入： "(()(()))"
输出： 6
?

提示：

S?是平衡括号字符串，且只含有?(?和?)?。
2 <= S.length <= 50

?

方法一：递归+分治

遍历字符串，如果当前字符串是(，那么t+=1，如果是)，那么t-=1。之后进行判断t==0，如果等于0的话，而且当前位置的前一个位置正好是(，即k-i==1，说明匹配了一个()，此时结果score+=1。否则的话说明从i-k之间存在嵌套的()，因此score=2*helper(i+1,k)，然后再从i=k+1开始遍历。

class Solution:
    def scoreOfParentheses(self,S: str) -> int:
        def helper(i,j):
            score=0
            t=0
            for k in range(i,j):
                if S[k]=="(":
                    t+=1
                else:
                    t-=1
                if t == 0:
                    if k-i==1:
                        score+=1
                    :
                        score+=2*helper(i+1,k)
                    i=k+1
            return score
        return helper(0,len(S))

方法二：栈

字符串 S 中的每一个位置都有一个“深度”，即该位置外侧嵌套的括号数目。例如，字符串 (()(.())) 中的 . 的深度为 2，因为它外侧嵌套了 2 层括号：(__(.__))。

我们用一个栈来维护当前所在的深度，以及每一层深度的得分。当我们遇到一个左括号 ( 时，我们将深度加一，并且新的深度的得分置为 0。当我们遇到一个右括号 ) 时，我们将当前深度的得分乘二并加到上一层的深度。这里有一种例外情况，如果遇到的是 ()，那么只将得分加一。

下面给出了字符串 (()(())) 每次对应的栈的情况：

[0,0] (
[0,0] ((
[0,1] (()
[0,1,0] (()(
[0,0] (()((
[0,1] (()(()
[0,3] (()(())
[6] (()(()))

 Solution(object):
     scoreOfParentheses(self,S):
        stack = [0] #The score of the current frame

        for x  S:
            if x == '':
                stack.append(0)
            :
                v = stack.pop()
                stack[-1] += max(2 * v,1)

         stack.pop()

方法三：统计核心数目

事实上，我们可以发现，只有 () 会对字符串 S 贡献实质的分数，其它的括号只会将分数乘二或者将分数累加。因此，我们可以找到每一个 () 对应的深度 x，那么答案就是 2^x 的累加和。

 0
        for i,x  enumerate(S):
            :
                bal += 1
            :
                bal -= 1
                if S[i-1] == :
                    ans += 1 << bal
         ans

?

参考链接：https://leetcode-cn.com/problems/score-of-parentheses/solution/gua-hao-de-fen-shu-by-leetcode/

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!