Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-stack
class Solution:
"""
Greedy+stack:
We use stack to keep track of index of unmatched parentheses.
Top of stack is nearest index of unmatched parenthese.
We traverse the given string forward.
Initally, we put -1 in the stack.
如果又括號就進stack, 左括號就出stack, 然後計算長度
when encounter the open parenthese, we append the index
when encounter the close parenthese,
stack.pop() # pop unmatched parentheses
if stack is empty, it means there's no valid parentheses
we append the index
else:
# the valid length is current idx - nearest index of unmatched parenthese
length = idx - stack[-1]
"()"
stack=[-1]
1-(-1) = 2
Ref:
https://www.youtube.com/watch?v=39CEPFCl5sE&ab_channel=LeetCode%E5%8A%9B%E6%89%A3
"""
def longestValidParentheses(self, s: str) -> int:
"""
Stack
T:O(n)
S:O(n)
"""
n = len(s)
if n <=1 :
return 0
stack = collections.deque([-1])
max_len = 0
for i in range(n):
char = s[i]
if char == "(":
stack.append(i)
elif char == ")":
stack.pop()
if len(stack) == 0:
stack.append(i)
else:
# calculate length of valid parentheses
length = i - stack[-1]
max_len = max(max_len, length)
return max_len
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment