856. Score of Parentheses-白红宇的个人博客

856. Score of Parentheses

发布日期：2021-05-09 02:51:25 浏览次数：22 分类：博客文章

本文共 1533 字，大约阅读时间需要 5 分钟。

Given a balanced parentheses string S, compute the score of the string 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 strings

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

Approach #1. DFS. [Java]

class Solution {    public int scoreOfParentheses(String S) {        return helper(S, 0, S.length() - 1);    }        public int helper(String S, int l, int r) {        if (l + 1 == r) return 1;        int b = 0;        for (int i = l; i < r; ++i) {            if (S.charAt(i) == '(') b++;            else b--;            if (b == 0) return helper(S, l, i) + helper(S, i+1, r);        }        return 2 * helper(S, l + 1, r - 1);    }}

��

Approach #2: Stack. [Java]

class Solution {    public int scoreOfParentheses2(String S) {        boolean mode = true;        int ret = 0;        Stack
    
      stack = new Stack<>();        for (int i = 0; i < S.length(); ++i) {            if (S.charAt(i) == ')' && mode) {                ret += Math.pow(2, stack.size() - 1);                mode = false;                stack.pop();            } else if (S.charAt(i) == '(') {                stack.push('(');                mode = true;            } else {                stack.pop();            }        }        return ret;    }}

��

上一篇：899. Orderly Queue

下一篇：833. Find And Replace in String

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章