32. Longest Valid Parentheses
https://leetcode.com/problems/longest-valid-parentheses/
solution
动态规划
以s[i]结尾的字符串能够构成的最长的匹配串的长度
# https://zhuanlan.zhihu.com/p/110240060
时间复杂度:O() 空间复杂度:O()
经典做法
一个栈维护左括号的下标,然后遇到匹配的右括号时弹出左括号并通过下标计算长度
class Solution:
def longestValidParentheses(self, s: str) -> int:
max_len = 0
stack = [-1]
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
max_len = max(max_len, i - stack[-1])
return max_len
follow op
Last updated