Stay Hungry.Stay Foolish.

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

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

⬆️

写的不错,帮助到了您,赞助一下主机费~

扫一扫,用支付宝赞赏
扫一扫,用微信赞赏
LeetCode1-5 2018-03-01

暂无评论~~