##### 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();
}
}

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

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
}