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 1AB
has scoreA + B
, where A and B are balanced parentheses strings.(A)
has score2 * 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:
S
is a balanced parentheses string, containing only(
and)
.2 <= S.length <= 50
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 }