原题链接在这里：https://leetcode.com/problems/score-of-parentheses/
题目：
Given a balanced parentheses string S, compute the score of the string based on the following rule:
() has score 1AB 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: "()"
Output: 1
Example 2:
Input: "(())"
Output: 2
Example 3:
Input: "()()"
Output: 2
Example 4:
Input: "(()(()))"
Output: 6
Note:
S is a balanced parentheses string, containing only ( and ).2 <= S.length <= 50题解：
When encountering (, push current result to stack and set cur to 0.
When encountering ), pop the stack and plus max(current value * 2, 1). Assign it back to current number.
Time Complexity: O(n). n = S.length().
Space: O(n).
AC Java:
1 class Solution { 2 public int scoreOfParentheses(String S) { 3 int cur = 0; 4 Stack<Integer> stk = new Stack<>(); 5 for(char c : S.toCharArray()){ 6 if(c == ‘(‘){ 7 stk.push(cur); 8 cur = 0; 9 }else{ 10 cur = stk.pop() + Math.max(2*cur, 1); 11 } 12 } 13 14 return cur; 15 } 16 }
When encounter (), we care how many layers of parentheses are outside of this ().
We could have l to accumlate this. (, l++. ), l--.
And when (), accumlate 1<<l into result.
Time Complexity: O(n). n = S.length().
Space: O(1).
AC Java:
1 class Solution { 2 public int scoreOfParentheses(String S) { 3 int res = 0; 4 int l = 0; 5 for(int i = 0; i<S.length(); i++){ 6 char c = S.charAt(i); 7 if(c == ‘(‘){ 8 l++; 9 }else{ 10 l--; 11 } 12 13 if(c == ‘)‘ && S.charAt(i-1) == ‘(‘){ 14 res += 1<<l; 15 } 16 } 17 18 return res; 19 } 20 }
LeetCode 856. Score of Parentheses
原文：https://www.cnblogs.com/Dylan-Java-NYC/p/11986867.html