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.
1using System;
2using System.Collections.Generic;
3
4public class Program
5{
6 public static int ScoreOfParentheses(string s)
7 {
8 Stack<int> stack = new Stack<int>();
9 stack.Push(0); // Base score
10
11 foreach (char ch in s)
12 {
13 if (ch == '(')
14 {
15 stack.Push(0);
16 }
17 else
18 {
19 int score = stack.Pop();
20 stack.Push(stack.Pop() + Math.Max(2 * score, 1));
21 }
22 }
23
24 return stack.Pop();
25 }
26
27 public static void Main()
28 {
29 string s = "(())";
30 Console.WriteLine("Score: " + ScoreOfParentheses(s));
31 }
32}The C# approach mirrors the stack mechanism for score management. This involves processing characters one by one and updating scores of levels when a closing parenthesis is encountered, ensuring each score is accurately calculated with respect to its nesting.
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.