LeetCode-32 New

Longest Valid Parentheses

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

Example 1:

Solution:

1.使用栈：

首先将-1放入栈中，然后每次遇到 '(' 就将其下标入栈，每遇到 ')' 就出栈，并计算当前有效的字符串长度。当出栈后栈变为空，并将当前下标入栈。并保持记录最长字串。

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

2.动态规划：

声明 dp 数组，长度和字符串总长度一致。dp 数组的第 i 个元素代表以 i 结尾的最长子串的长度。初始 dp全为0。有效子串肯定是以 ')' 结尾，因此分为两种情况：

1. s[i] = ')' and s[i - 1] = '(' , 此时 dp[i] = dp[i - 2] + 2
2. s[i] = ')' and s[i - 1] = ')' , 此时 dp[i] = dp[i - 1] + dp[i - dp[i-1] - 2] + 2

class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_length = 0
        dp = [0] * len(s)
        for i in range(1, len(s)):
            if s[i] == ')':
                if s[i - 1] == '(':
                    dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
                elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(':
                    dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) + 2
                max_length = max(max_length, dp[i])
        return max_length