856. Score of Parentheses (medium)

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule:

• "()" has score 1.
• AB has score A + B, where A and B are balanced parentheses strings.
• (A) has score 2 * A, where A is a balanced parentheses string.

 

Example 1:

Input: s = "()"
Output: 1

Example 2:

Input: s = "(())"
Output: 2

Example 3:

Input: s = "()()"
Output: 2

 

Constraints:

• 2 <= s.length <= 50
• s consists of only '(' and ')'.
• s is a balanced parentheses string.

A:

花了2个番茄钟才做出来

核心观点， 记录层数，只有在最里侧的（）才需要根据层数，计算score

class Solution {

public:

int scoreOfParentheses(string s) {

int nLayer = 0, score = 0;

for (int i = 0; i < s.size(); i++) {

if (s[i] == '(') {

nLayer++;

} else { // ch == ')'

if (i > 0 && s[i - 1] == '(')

score += pow(2, nLayer - 1);

nLayer--;

}

}

return score;

}

};

下面的是别人用stack计算的。 我自己一开始没想出来

https://leetcode.com/problems/score-of-parentheses/solutions/1856519/java-c-visually-explained/

Okay, so first thing came in our mind is can we solve this problem using stack, and I say yes we'll solve this problem using stack.

• First create one stack of Integer not Character
• So, as we are using Integer, what we gonna put in stack is intially 0 when we encounter (
• And we'll calculate the score when we encounter )

Let's Understand it visually :-

class Solution {

public:

int scoreOfParentheses(string s) {

stack<int> st;

int score = 0;

for (int i = 0; i < s.size(); i++) {

if (s[i] == '(') {

st.push(score);

score = 0;

} else {

score = st.top() + max(2 * score, 1);

st.pop();

}

}

return score;

}

};