LeetCode 856. 括号的分数之json解法

发表于
本文字数： 2.3k | 阅读时长 ≈ 2 分钟

原题内容：

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

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

示例 1：

1
2
输入： "()"
输出： 1
1
2
3
4
5
6


>
> **示例 2：**
>
>

输入： “(())”
输出： 2

1
2

**示例 3：**

输入： “()()”
输出： 2

1
2


示例 4：

1
2
输入： "(()(()))"
输出： 6

提示：

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

模板：

1
2
3
4
5
6
class Solution:
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """

思路：

我的第一想法是利用 Json ，把所传入的字符串 S 里的所有 () 替换为 []，然后在字符串合适的位置加上逗号，以此将字符串转化为 json 能识别的字符串，再转化为 Python list 对象，最后用一个递归函数求得这个 list 的“分数”。

设计：

考虑所有情况。

如果要把字符串 "(()(()))" 转化为 json 认识的字符串，那应该是 [[ ], [[ ]]] 。但是要注意，json 不认识 [],[] 这样的字符串（里面有两个 list ），于是我们干脆把所有传进来的原字符串外面套一个 [] 。省得去分情况判断，这样的话因为外面加一个括号会使得得到的值 乘以2 所以我们在最后返回值的时候应该将结果 除以2 。

  1. 我们能发现逗号出现的地方一定是原字符串反括号接正括号的地方—— )( -> ],[ ，这是第一项替换。

  2. 所有的小括号替换成中括号，这是第二项替换。

  3. 把上一步得到的字符串用 [ ] 框起来，这是第三项替换。

我们来实现这部分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """
        import json  # 导入json库
        # Step. 1
        S = S.replace(')(', '],[')
        # Step. 2
        S = S.replace('(', '[')
        S = S.replace(')', ']')
        # Step. 3
        S = json.loads('[' + S + ']')  	# 此处多一个外括号，是因为json一次只能load一个list，最后记得要除以2，就抵消了

通过这三步就把 S 转化成了一个服服帖帖的 list 对象而不再是 str 对象。接下来我们考虑计算“分数”的部分。

直接上代码了，很简洁：

1
2
3
4
5
6
7
8
9
# 注意缩进，保持在scoreOfParentheses函数之内        
def cal(l):
    if l == []:  # 递归的终点                
        return 1  # （）得1分
    else:
        r = 0
        for t in l:	
            r += cal(t)	# AB 得 A + B 分
        return 2 * r	# (A) 得 2 * A 分

最后 return 调用cal() 函数，并将得到的值除以2就行了，因为我们在字符串外面多套了一个 []。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """
        import json
        S = S.replace(')(', '],[')
        S = S.replace('(', '[')
        S = S.replace(')', ']')
        S = json.loads('[' + S + ']')  # 此处多一个外括号，是因为json一次只能load一个list，最后除以2就抵消了
        print(S)
        def cal(l):
            if l == []:
                print(1)
                return 1
            else:
                r = 0
                for t in l:
                    r += cal(t)
                return 2 * r
        return int(cal(S) / 2)