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

概述给定一个平衡括号字符串 S，按下述规则计算该字符串的分数： () 得 1 分。AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。(A) 得 2 *

给定一个平衡括号字符串 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/

总结

以上是内存溢出为你收集整理的【python-leetcode856-子集】括号的分数全部内容，希望文章能够帮你解决【python-leetcode856-子集】括号的分数所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。