leetcode: 32. Longest Valid Parentheses [✗]

Problem

# Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
#   
# For "(()", the longest valid parentheses substring is "()", which has length = 2.
#   
# Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

AC

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        maxlen = 0
        start = -1
        for i, c in enumerate(s):
            if c=='(':
                if start>=0:
                    stack.append((c, start))
                    start = -1
                else:
                    stack.append((c, i))
            else:
                if stack and stack[-1][0]=="(":
                    length = i-stack[-1][1]+1
                    if length>maxlen:
                        maxlen = length
                    start = stack[-1][1]
                    stack.pop()
                else:
                    start = -1
                    stack.append((c, i))
        return maxlen


if __name__ == "__main__":
    assert Solution().longestValidParentheses("()") == 2
    assert Solution().longestValidParentheses(")()())") == 4

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券