From Leetcode 856 Score of Parentheses
1. Problem Description
Given a balanced parentheses string s
, return the score of the string.
The score of a balanced parentheses string is based on the following rule:
"()"
has score1
.AB
has scoreA + B
, whereA
andB
are balanced parentheses strings.(A)
has score2 * A
, whereA
is a balanced parentheses string.
1.1 Solution
we use stack to solve this problem:
- If there is a
(
, we add it to stack because it must match with a)
to get valid value back; - If there is a
)
, we can try to match it with the top value in stack: - we can either
+1
or*2
, here is a tricky way to tackle it: we always choose the greater one :(2 * last) or 1
def scoreOfParentheses(self, s: str) -> int:
# Create stack
stack = [0]
for c in s:
if c == "(":
stack.append(0)
else:
last = stack.pop()
stack[-1] += (2 * last) or 1
print(stack)
return stack[-1]