Algorithm
Problem Name: 856. Score of Parentheses
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 score1.ABhas scoreA + B, whereAandBare balanced parentheses strings.(A)has score2 * A, whereAis 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 <= 50sconsists of only'('and')'.sis a balanced parentheses string.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public int scoreOfParentheses(String S) {
Stack stack = new Stack<>();
int currMultiplier = 0;
for (char c : S.toCharArray()) {
if (c == '(') {
stack.push(currMultiplier);
currMultiplier = 0;
} else {
currMultiplier = stack.pop() + Math.max(2 * currMultiplier, 1);
}
}
return currMultiplier;
}
}
Input
s = "()"
Output
1
#2 Code Example with Javascript Programming
Code -
Javascript Programming
/**
* @param {string} S
* @return {number}
*/
const scoreOfParentheses = function(S) {
let res = 0,
bal = 0;
for (let i = 0; i < S.length; i++) {
if (S.charAt(i) === "(") {
bal += 1;
} else {
bal -= 1;
if (S.charAt(i - 1) === "(") {
res += 1 << bal;
}
}
}
return res;
};
Input
s = "()"
Output
1
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def scoreOfParentheses(self, S):
stack, res = [], 0
for c in S:
if c == "(":
stack.append(0)
else:
add = 2 * stack.pop() or 1
if stack:
stack[-1] += add
else:
res += add
return res
Input
s = "(())"
Output
2
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0856_ScoreOfParentheses
{
public int ScoreOfParentheses(string S)
{
var balance = 0;
var result = 0;
for (int i = 0; i < S.Length; i++)
{
if (S[i] == '(') balance++;
else
{
balance--;
if (S[i - 1] == '(')
result += 1 << balance;
}
}
return result;
}
}
}
Input
s = "(())"
Output
2