中等

问题描述

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

• () 得 1 分。
• AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
• (A) 得 2 * A 分，其中 A 是平衡括号字符串。

示例 1：

输入： "()"
输出： 1

示例 2：

输入： "(())"
输出： 2

示例 3：

输入： "()()"
输出： 2

示例 4：

输入： "(()(()))"
输出： 6

提示：

• S 是平衡括号字符串，且只含有 ( 和 )。
• 2 <= S.length <= 50

深度优先搜索

遍历字符串，若 "(" 后为 ")"，这个情况得 1 分，若 "(" 后为 "("，则递归处理后一个字符开始的子字符串，得到其分数后 $\times 2$，递归结束后即为最终分数。

/**
 * @param {string} s
 * @return {number}
 */
var scoreOfParentheses = function (s) {
  const n = s.length
  let idx = 0
  const dfs = () => {
    let sum = 0
    while (idx < n && s[idx] === '(') {
      idx++
      if (s[idx] === ')') {
        sum += 1
      } else {
        sum += dfs() * 2
      }
      idx++
    }
    return sum
  }
  return dfs()
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$