[String]032 Longest Valid Parentheses

• 分类：String

• 考察知识点：String

• 最优解时间复杂度：O(n)

• 最优解空间复杂度：O(n)

32. Longest Valid Parentheses

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 "()()"

代码：

stack方法:

class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack=[]
        start=-1
        res=0
        
        for i,ch in enumerate(s):
            if ch=="(":
                stack.append(i)
            else:
                if len(stack)==0:
                    start=i
                else:
                    stack.pop()
                    if len(stack)==0:
                        res=max(res,i-start)
                    else:
                        res=max(res,i-stack[-1])
                        
        return res

讨论：

1.这道题有两种做法，一种stack一种DP
2.凡是看见括号的题目脑子里就一定要想到stack！！！
3.DP方法非到万不得已不要去用，不仅很难想，状态转移很难，而且很容易错
4.start是指前-后+1的（后+1）的部分，可以这么理解

加油