Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

describe

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule:

  • “()” has score 1.
  • AB has score A + B, where A and B are balanced parentheses strings.
  • (A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: s = "()"
Output: 1
Copy the code

Example 2:

Input: s = "(())"
Output: 2
Copy the code

Example 3:

Input: s = "()()"
Output: 2
Copy the code

Example 4:

Input: s = "(()(()))"
Output: 6
Copy the code

Example 5:

Note:

2 <= s.length <= 50
s consists of only '(' and ')'.
s is a balanced parentheses string.
Copy the code

parsing

= = = = = = = = = = = = = =

  • For phi, the fraction is 1
  • For combinations of type A+B, the score is the score of A plus the score of B
  • For combinations of type (A), the score is twice the score of A

In fact, for the parenthesis type of problems, the inherent properties of the stack structure can be solved, this problem is the same but need to be combined with the meaning of the problem to change. Example 4 is used here to illustrate the stack. When we encounter (when we deepen the parenthesis depth, the new depth is 0, encountered), we multiply the previous score by two, except that the score of () is 1, and the result is as follows:

  • [0] init stack
  • [0, 0] after parsing (
  • [0, 0, 0] after (
  • [0, 1] after )
  • [0, 1, 0] after (
  • [0, 1, 0, 0] after (
  • [0, 1, 1] after )
  • [0, 3] after )
  • [6] after )

The final stack[-1] is the answer.

answer

class Solution(object):
    def scoreOfParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [0]
        for c in s:
            if c == '(':
                stack.append(0)
            elif c == ')':
                t = stack.pop()
                stack[-1] += max(2*t, 1)
        return stack[-1]

        	      
		
Copy the code

The results

Given the submission in the Python online submission. Memory Usage: 10 ms Submissions in Python online submissions for Score of Parentheses.Copy the code

parsing

If we know the depth d of each pair of (), we can get the score of 2^d (1>>d) and add it to the result. As in Example 4 (()(())) :

  • The first occurrence has a depth of () of 1 and its score is 1>>1
  • The second occurrence of () depth 2 has a score of 1>>2
  • Add them together and you get answer 6

answer

class Solution(object):
    def scoreOfParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        result, balance = 0, 0
        for i,c in enumerate(s):
            if c=='(':
                balance += 1
            else:
                balance -= 1
                if s[i-1] == '(':
                    result += 1 << balance
        return result
Copy the code

The results

The submission in the Python online submission list has the following status: Submissions in Python online submissions for Score of Parentheses.Copy the code

Original link: leetcode.com/problems/sc…

Your support is my biggest motivation