54 lines
1.8 KiB
Python
54 lines
1.8 KiB
Python
def scoreOfParentheses(s):
|
|
"""
|
|
:type s: str
|
|
:rtype: int
|
|
"""
|
|
# Attempted Solution
|
|
# score = left = right = 0
|
|
|
|
# for x in s:
|
|
# if x == "(":
|
|
# left += 1
|
|
# score += 1
|
|
# elif x == ")":
|
|
# right += 1
|
|
# score += 1
|
|
# if (left + right) % 2 == 0:
|
|
# score /= 2
|
|
# return score
|
|
|
|
# 96% faster solution
|
|
# Initialize an empty list 'a', the length of the input string 's' as 'n'
|
|
a, n = [], len(s)
|
|
|
|
# Initialize 'c' and 't' to 0.
|
|
c = t = 0
|
|
|
|
# Loop through the characters of the input string, starting from the second character (index 1).
|
|
for i in range(1, n):
|
|
print(f'c is {c}')
|
|
print(t)
|
|
# If the current character is an opening parenthesis '('
|
|
if s[i] == '(':
|
|
# Increment the temporary variable 't' to keep track of the depth of nesting.
|
|
t += 1
|
|
# If the current character is a closing parenthesis ')', and the previous character was an opening parenthesis '('
|
|
elif s[i - 1] == '(':
|
|
# Calculate the score for the current balanced pair of parentheses and add it to 'c'.
|
|
# The score is 2 raised to the power of 't' (2^t).
|
|
c += 1 << t
|
|
|
|
# Decrease the temporary variable 't' as the current nested pair is closed.
|
|
t -= 1
|
|
else:
|
|
# If the current character is a closing parenthesis ')' and the previous character was also a closing parenthesis ')',
|
|
# simply decrease the temporary variable 't' to indicate the decrease in the depth of nesting.
|
|
t -= 1
|
|
|
|
# Return the total score of the balanced parentheses expression, stored in 'c'.
|
|
return c
|
|
|
|
# print(scoreOfParentheses("()")) # 1
|
|
print(scoreOfParentheses("(()(()))")) # 6
|
|
# print(scoreOfParentheses("()()()")) # 3
|