題目

給定一個平衡括號字串 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、遍歷；時間複雜度O(n)，空間複雜度O(1)

func scoreOfParentheses(S string) int {	res := 0	count := 0	for i := 0; i < len(S); i++ {		if S[i] == '(' {			count++		} else {			count--			if S[i-1] == '(' {				res = res + 1<<count			}		}	}	return res}

2、棧輔助；時間複雜度O(n)，空間複雜度O(n)

func scoreOfParentheses(S string) int {	stack := make([]int, 0)	stack = append(stack, 0)	for i := 0; i < len(S); i++ {		if S[i] == '(' {			stack = append(stack, 0)		} else {			a, b := stack[len(stack)-1], stack[len(stack)-2]			stack = stack[:len(stack)-2]			stack = append(stack, b+max(2*a, 1))		}	}	return stack[0]}func max(a, b int) int {	if a > b {		return a	}	return b}

3、分治；時間複雜度O(n^2)，空間複雜度O(n)

func scoreOfParentheses(S string) int {	return dfs(S, 0, len(S))}func dfs(S string, left, right int) int {	res := 0	count := 0	for i := left; i < right; i++ {		if S[i] == '(' {			count++		} else {			count--		}		if count == 0 {			if i-left == 1 {				res++			} else {				res = res + 2*dfs(S, left+1, i)			}			left = i + 1		}	}	return res}

總結

Medium題目，多種解法