Sponsored
Sponsored
This approach leverages a stack to manage the scores of the balanced parentheses string. As we iterate through the string:
At the end of the iteration, the top of the stack will contain the total score.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to the stack usage that can store one element per character in the worst case.
1function scoreOfParentheses(s) {
2 const stack = [0]; // Base score
3
4 for (const ch of s) {
5 if (ch === '(') {
6 stack.push(0);
7 } else {
8 const score = stack.pop();
9 stack[stack.length - 1] += Math.max(2 * score, 1);
10 }
11 }
12
13 return stack.pop();
14}
15
16console.log("Score:", scoreOfParentheses("(())"));In JavaScript, a stack is simulated using an array. By carefully pushing and popping scores, we can calculate and accumulate scores at each level of nested parentheses, handling single pairs immediately and larger nested structures cumulatively.
This approach iteratively computes the score by tracking the depth of parentheses:
Time Complexity: O(n), dictated by the string length.
Space Complexity: O(1), since the depth array size is fixed by constraint.
public class Program
{
public static int ScoreOfParentheses(string s)
{
int[] score = new int[50];
int depth = 0;
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '(')
{
depth++;
}
else
{
depth--;
score[depth] += s[i - 1] == '(' ? 1 : 2 * score[depth + 1];
score[depth + 1] = 0;
}
}
return score[0];
}
public static void Main()
{
string s = "((()))";
Console.WriteLine("Score: " + ScoreOfParentheses(s));
}
}C# uses an array like the other iterative approaches to handle scores by depth, adjusting for transitions between parenthesis types, and ensuring deeper scores are collated to surface effectively.