Fork me on GitHub

Longest Valid Parentheses

Posted on

Description

https://leetcode.com/problems/longest-valid-parentheses/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s is None or len(s) == 0 or len(s) == 1:
            return 0
        dp = [0 for i in range(len(s))]
        max_valid = 0
        for i in range(1, len(dp)):
            if s[i] == '(':
                dp[i] = 0
            else:
                if s[i - 1] == '(':
                    dp[i] = (2 if i < 2 else (dp[i - 2] + 2) )
                else:
                    temp = dp[i - 1]
                    if i - temp - 1 >= 0 and s[i - temp - 1] == '(':
                        dp[i] = temp + 2 + (0 if i - temp - 2 < 0 else dp[i - temp - 2])
                    else:
                        dp[i] = 0
            
            max_valid = max(max_valid, dp[i])
          
        print (dp)
            
        return max_valid