#32 Longest Valid Parentheses——Top 100 Liked Questions

柔情只为你懂 2022-02-01 00:06 180阅读 0赞

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

**Example 1:**

Input: "(()"
    Output: 2
    Explanation: The longest valid parentheses substring is "()"

**Example 2:**

Input: ")()())"
    Output: 4
    Explanation: The longest valid parentheses substring is "()()"

> """
> 
> 第一次：使用栈，找到所有有效的括号，并且保存其索引。将索引按照递增顺序排列，找其中连续索引最长的序列长度就是所求。求连续索引最长的序列长度的程序，完全就是凑出来的o(╯□╰)o  
> """
> 
> class Solution(object):  
>     def longestValidParentheses(self, s):  
>         """  
>         :type s: str  
>         :rtype: int  
>         """  
>         if not s or s ==')': return 0  
>         stack = \[\]  
>         index = \[\]  
>         res = \[\]  
>         for i, b in enumerate(s):  
>             if b == '(':  
>                 stack.append(b)  
>                 index.append(i)  
>             if b == ')':  
>                 if not stack:  
>                     continue  
>                 else:  
>                     check = stack.pop()  
>                     ind = index.pop()  
>                     if check == '(':  
>                         res.append(ind)  
>                         res.append(i)  
>     
>         res.sort()  
>         count = 0  
>         left = 0  
>         for j in range(len(res) - 1):  
>             if res\[j\] + 1 == res\[j + 1\]:  
>                 if j != len(res) - 2:  
>                     continue  
>                 else:  
>                     tmp = j + 1 - left + 1  
>                     return max(count, tmp)
> 
>             tmp = j - left + 1  
>             left = j + 1  
>             count = max(tmp, count)       
>         return count
> 
> """
> 
> Runtime: 60 ms, faster than 18.61% of Python online submissions for Longest Valid Parentheses.
> 
> Memory Usage: 12.9 MB, less than 5.55% of Python online submissions for Longest Valid Parentheses.
> 
> """

> """
> 
> 第二次：抄网上代码，动态规划解法，不懂啊，主要分两种情况：1）以‘）’结尾；2）以‘））’结尾
> 
> """ 
> 
>     class Solution:
>         def longestValidParentheses(self, s: str) -> int:
>             
>             if len(s) == 0:
>                 return 0
>             n = len(s)
>             dp = [0] * n
>             res = 0
>             for i in range(n):
>                 if i > 0 and s[i] == ')':
>                     if s[i - 1] == '(':
>                         dp[i] = dp[i -2] + 2
>                     elif s[i - 1] == ')' and i - dp[i - 1] - 1 >= 0 and s[i - dp[i-1] - 1] == '(':
>                         dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
>                 if res < dp[i]:
>                     res = dp[i]
>             return res
> 
> """
> 
> Runtime: 40 ms, faster than 99.96% of Python3 online submissions for Longest Valid Parentheses.
> 
> Memory Usage: 13.3 MB, less than 9.36% of Python3 online submissions for Longest Valid Parentheses.
> 
> """