856

856. Score of Parentheses (Medium)

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

Example 2:

Input: s = "(())"
Output: 2

Example 3:

Input: s = "()()"
Output: 2

 

Constraints:

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

Companies:
Facebook, Amazon

Related Topics:
String, Stack

Solution 1. Divide and Conquer

// OJ: https://leetcode.com/problems/score-of-parentheses/
// Author: github.com/lzl124631x
// 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));
    }
};

Or

// OJ: https://leetcode.com/problems/score-of-parentheses/
// Author: github.com/lzl124631x
// 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 2. DFS

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

Soltuion 3. Stack

// OJ: https://leetcode.com/problems/score-of-parentheses/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> st{{0}};
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                if (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/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> st{{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 4.

We only add to the answer when we see (). Assume it's at depth depth, we add 2^depth to the answer.

// OJ: https://leetcode.com/problems/score-of-parentheses/
// Author: github.com/lzl124631x
// 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] == '(') {
                if (s[i + 1] == ')') ans += (1 << depth), ++i;
                else ++depth;
            } else --depth;
        }
        return ans;
    }
};