My dp solution using stack


  • 0
    H
    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            stack = [] 
            dp = [0 for _ in range(len(s) + 1)]
            for i, c in enumerate(s):
                if c == '(':
                    dp[i + 1] = 0
                    stack.append(c)
                else:
                    dp[i + 1]=dp[i] + 2 if stack and stack.pop() == '(' else 0
                    if i + 1 - dp[i + 1] > 0:
                        dp [i + 1] += dp [i + 1 - dp [i + 1]]
            return max(dp)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.