32. Longest Valid Parentheses

[mengyushi]

DP

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        '''
        DP

        '.....()'
        dp[i] = 2+dp[i-2]

        '.......((........))'
                 | dp[i-1]|
                | dp[i-1]+2||
            dp[i] = dp[i-1-dp[i-1]-1] + dp[i-1]+2

        Time Complexity: O(N)
        Space Complexity: O(N)

        '''

        if not s:
            return 0
        N = len(s)
        dp = [0]*N

        for i in range(1,N):
            if s[i] == ')': # "....(" never valid. Always 0.
                if i>0 and s[i-1] == '(':
                    dp[i] = 2+dp[i-2]
                elif i-dp[i-1]-1>=0 and s[i-dp[i-1]-1] == "(":
                    dp[i] = 2+dp[i-1]+dp[i-dp[i-1]-2]
        return max(dp)

Stack

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        '''
        stack[0]: last invalued position

        )()())

        stack = [-1]

        i = 0, )
        stack = []
        stack = [0]

        i = 1, (
        stack = [0,1]

        i = 2, )
        stack = [0]
        length = max(0,2-0) = 2

        i = 3, (
        stack = [0,3]

        i = 4, )
        stack = [0]
        length = max(0,4-0) = 4

        i = 5, )
        stack = []
        stack = [5]

        '''
        length, stack = 0, [-1]

        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    length = max(length, i-stack[-1])

        return length