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.
This JavaScript implementation leverages an array to manipulate scores by depth directly, ensuring that computation of nested and simple structures remains straightforward and logical without additional memory overhead.