leetcode讲解--856. 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: 1Example 2:Input: “(())“Output: 2Example 3:Input: “()()“Output: 2Example 4:Input: “(()(()))“Output: 6Note:S is a balanced parentheses string, containing only ( and ).2 <= S.length <= 50题目地址讲解这道题分类都有点难，可以算在智力题里面。主要是要理解一个套路：”(()(()))” -> “(())” + “((()))” = 2 + 4这样就会发现，可以维护一个层数变量，然后遍历的时候，遇到’(‘就加一，遇到”)“就减一，遇到”()“这一对，就相当于找到了一组。然后把找到的所有组相加就行了。java代码class Solution { public int scoreOfParentheses(String S) { int d = -1; int result = 0; for(int i=0;i<S.length();i++){ d += S.charAt(i)==’(’?1:-1; if(S.charAt(i)==’(’ && S.charAt(i+1)==’)’){ result += 1 << d; } } return result; }}