LC 856

Solution to LeetCode 856 Score of Parentheses.

LeetCode 856

Score of Parentheses (Medium). [link]

1. Recursion. The work flow of recursion for this problem:

score("((()))")
= 2 * score("(())")
= 2 * (2 * score("()"))
= 2 * (2 * 1)
= 2

score("()(()())")
= score("()") + score("(()())")
= 1 + 2 * score("()()")
= 1 + 2 * (score("()") + score("()"))
= 1 + 2 * (1 + 1)
= 5

Time complexity O(n) ~ O(n^2). Space complexity O(n).

class Solution(object):
    def scoreOfParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        def score(string, l, r):
            if r - l == 1: return 1
            b = 0
            for i in range(l, r):
                if string[i] == '(':
                    b += 1
                if string[i] == ')':
                    b -= 1
                if b == 0:
                    return score(string, l, i) + score(string, i+1, r) # ()()
            return 2 * score(string, l + 1, r - 1) # (())
        return score(s, 0, len(s) - 1)

2. Counting. Find the number d of balanced parentheses are outside of each (), then the score of it is 2^(d-1). E.g. “()”, d = 1, 2^(d-1) = 1; “(())”, d = 2, 2^(d-1) = 2, “(()(()()))”, d1 = 2, d2 = 3, d3 = 3, ans = 2^1 + 2^2 + 2^2 = 10.

   Time complexity O(n), space complexity O(1).

class Solution(object):
    def scoreOfParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        res = 0
        d = -1
        for i in range(len(s)):
            if s[i] == "(":
                d += 1
            else:
                d -= 1
            if s[i] == '(' and s[i+1] == ')':
                res += 2 ** d
        return res