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.
Using a list to simulate depth, this Python solution tracks scores with manipulations based on the transitions from open to close parentheses. Resetting higher depth scores ensures accuracy in nested parentheses calculations.