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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int scoreOfParentheses(char *s) {
5 int stack[50]; // Constraint allows for up to 50
6 int top = -1;
7 stack[++top] = 0; // Start with a base score
8
9 while (*s) {
10 if (*s == '(') {
11 stack[++top] = 0;
12 } else {
13 int score = stack[top--];
14 stack[top] += (score > 0 ? 2 * score : 1);
15 }
16 s++;
17 }
18 return stack[0];
19}
20
21int main() {
22 char s[] = "(())";
23 printf("Score: %d\n", scoreOfParentheses(s));
24 return 0;
25}The C solution utilizes a simple stack array to keep track of scores at each level. As we parse the string, we push zero onto the stack for each '('. When encountering a ')', the score is calculated and added to the top of the stack. This method ensures that nested structures are calculated accurately by collapsing scores upwards through multiplication and addition.
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 Java approach uses an integer array to maintain scores at various depths, ensuring that scores are only accumulated when encountering ')'. Each depth value is adjusted appropriately based on the structure closed.