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.
1def score_of_parentheses(s):
2 stack = [0]
3 for ch in s:
4 if ch == '(':
5 stack.append(0)
6 else:
7 score = stack.pop()
8 stack[-1] += max(2 * score, 1)
9 return stack.pop()
10
11if __name__ == "__main__":
12 s = "(())"
13 print("Score:", score_of_parentheses(s))The Python solution uses a list as a stack to manage parentheses scores. For each closing parenthesis, it calculates the intermediate score, updates the previous level's score, and handles nested structures by doubling when necessary. This ensures accurate score calculation throughout nested levels.
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.