Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/856.html

856. Score of Parentheses (Medium)

Given a balanced parentheses string S, compute the score of the string 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: "()"
Output: 1

Example 2:

Input: "(())"
Output: 2

Example 3:

Input: "()()"
Output: 2

Example 4:

Input: "(()(()))"
Output: 6

 

Note:

  1. S is a balanced parentheses string, containing only ( and ).
  2. 2 <= S.length <= 50

Related Topics:
String, Stack

Solution 1. Divide and Conquer

// OJ: https://leetcode.com/problems/score-of-parentheses/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    int scoreOfParentheses(string S) {
        if (S == "()") return 1;
        int i = 0, left = 0;
        do {
            left += S[i++] == '(' ? 1 : -1;
        } while (left);
        if (i == S.size()) return 2 * scoreOfParentheses(S.substr(1, S.size() - 2));
        return scoreOfParentheses(S.substr(0, i)) + scoreOfParentheses(S.substr(i));
    }
};

Solution 2. Divide and Conquer

Same idea as Solution 1, but more space efficient.

// OJ: https://leetcode.com/problems/score-of-parentheses/
// Time: O(N^2)
// Space: O(N)
class Solution {
private:
    int score(string &S, int begin, int end) {
        if (begin + 2 == end) return 1;
        int i = begin, left = 0;
        do {
            left += S[i++] == '(' ? 1 : -1;
        } while (left);
        if (i == end) return 2 * score(S, begin + 1, end - 1);
        return score(S, begin, i) + score(S, i, end);
    }
public:
    int scoreOfParentheses(string S) {
        return score(S, 0, S.size());
    }
};

Solution 3. DFS

// OJ: https://leetcode.com/problems/score-of-parentheses/solution/
// Time: O(N)
// Space: O(N)
class Solution {
    int dfs(string &s, int &i) {
        int ans = 0;
        while (i < s.size() && s[i] == '(') { 
            if (i + 1 < s.size() && s[i + 1] == ')') {
                i += 2;
                ++ans;
            } else {
                ++i;
                ans += 2 * dfs(s, i);
                ++i;
            }
        }
        return ans;
    }
public:
    int scoreOfParentheses(string s) {
        int i = 0;
        return dfs(s, i);
    }
};

Soltuion 4. Stack

// OJ: https://leetcode.com/problems/score-of-parentheses/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> st;
        st.push(0);
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                if (i + 1 < s.size() && s[i + 1] == ')') {
                    ++i;
                    st.top()++;
                } else st.push(0);
            } else {
                int val = 2 * st.top();
                st.pop();
                st.top() += val;
            }
        }
        return st.top();
    }
};

Or

// OJ: https://leetcode.com/problems/score-of-parentheses/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> st;
        st.push(0);
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') st.push(0);
            else {
                int val = max(2 * st.top(), 1);
                st.pop();
                st.top() += val;
            }
        }
        return st.top();
    }
};

Solution 5.

// OJ: https://leetcode.com/problems/score-of-parentheses/solution/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/score-of-parentheses/solution/
class Solution {
public:
    int scoreOfParentheses(string S) {
        int ans = 0, depth = 0;
        for (int i = 0; i < S.size(); ++i) {
            if (S[i] == '(') ++depth;
            else {
                --depth;
                if (i - 1 >= 0 && S[i - 1] == '(') ans += 1 << depth;
            }
        }
        return ans;
    }
};

  • class Solution {
    public int scoreOfParentheses(String S) {
        if (S == null || S.length() == 0)
            return 0;
        Stack<Character> parenthesesStack = new Stack<Character>();
        Stack<Integer> scoreStack = new Stack<Integer>();
        int length = S.length();
        for (int i = 0; i < length; i++) {
            char c = S.charAt(i);
            if (c == '(') {
                parenthesesStack.push(c);
                scoreStack.push(0);
            } else {
                parenthesesStack.pop();
                int prevScore = scoreStack.pop();
                if (prevScore == 0)
                    scoreStack.push(1);
                else {
                    while (scoreStack.peek() != 0)
                        prevScore += scoreStack.pop();
                    scoreStack.pop();
                    scoreStack.push(prevScore * 2);
                }
            }
        }
        int totalScore = 0;
        while (!scoreStack.isEmpty())
            totalScore += scoreStack.pop();
        return totalScore;
    }
}

############

class Solution {
    public int scoreOfParentheses(String s) {
        int ans = 0, d = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                ++d;
            } else {
                --d;
                if (s.charAt(i - 1) == '(') {
                    ans += 1 << d;
                }
            }
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/score-of-parentheses/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    int scoreOfParentheses(string S) {
        if (S == "()") return 1;
        int i = 0, left = 0;
        do {
            left += S[i++] == '(' ? 1 : -1;
        } while (left);
        if (i == S.size()) return 2 * scoreOfParentheses(S.substr(1, S.size() - 2));
        return scoreOfParentheses(S.substr(0, i)) + scoreOfParentheses(S.substr(i));
    }
};

  • class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        ans = d = 0
        for i, c in enumerate(s):
            if c == '(':
                d += 1
            else:
                d -= 1
                if s[i - 1] == '(':
                    ans += 1 << d
        return ans

############

class Solution(object):
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """
        stack = []
        score = 0
        for c in S:
            if c == '(':
                stack.append("(")
            else:
                tc = stack[-1]
                if tc == '(':
                    stack.pop()
                    stack.append(1)
                else:
                    num = 0
                    while stack[-1] != '(':
                        num += stack.pop()
                    stack.pop()
                    stack.append(num * 2)
        return sum(stack)

  • func scoreOfParentheses(s string) int {
	ans, d := 0, 0
	for i, c := range s {
		if c == '(' {
			d++
		} else {
			d--
			if s[i-1] == '(' {
				ans += 1 << d
			}
		}
	}
	return ans
}

All Problems

All Solutions