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 <iostream>
2#include <stack>
3#include <string>
4
5int scoreOfParentheses(std::string s) {
6 std::stack<int> st;
7 st.push(0); // Base score
8
9 for (char ch : s) {
10 if (ch == '(') {
11 st.push(0);
12 } else {
13 int score = st.top(); st.pop();
14 int prevScore = st.top(); st.pop();
15 st.push(prevScore + (score > 0 ? 2 * score : 1));
16 }
17 }
18 return st.top();
19}
20
21int main() {
22 std::string s = "(())";
23 std::cout << "Score: " << scoreOfParentheses(s) << std::endl;
24 return 0;
25}The C++ solution uses a stack data structure to manage scores at each nested level of parentheses. Each '()' is initially represented as a score of 1, and nested pairs are calculated by popping the current score, doubling it if necessary, and then adding it to the previously accumulated score.
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.
In C, this iterative approach uses an array to track scores at different depths. It handles the transition from '(' to ')' by either recognizing single pairs or multiplying for nested structures. This approach exploits direct index manipulation for score calculations.