leetcode第32题解题报告

发表于 | 阅读次数:

题目：

  1. Longest Valid Parentheses

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

  • Example 1:

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

  • Example 2:

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

解题思路

  • 符号对的匹配首先想到的是用栈来解决，左括号压栈，右括号匹配和出栈

解法1:

  • 用栈stack存储左括号的索引，start标记栈中最底部左括号索引，遇到右括号判断stack，若为空，则记录当前位置的下一个索引为start；若非空, 则出栈一个元素，再次判断栈是否为空，为空则 max(res, index-start+1), 否则 max(res, index-stack[-1]) ;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        res, start, stack = 0, 0, []
        for index, c in enumerate(s):
            if c == "(":
                stack.append(index)
            else:
                if stack:
                    stack.pop()
                    res = max(res, index-stack[-1]) if stack else max(res, index-start+1)
                else:
                    start = index+1 # next ( position
        return res

解法2:

  • 使用动态规划
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def longestValidParentheses(self, s):
        length = len(s)
        if length == 0:
            return 0
        dp = [0] * length
        for i in range(1,length):
                #当遇到右括号时，尝试向前匹配左括号
            if s[i] == ')':
                pre = i - dp[i-1] -1;
                #如果是左括号，则更新匹配长度
                if pre>=0 and s[pre] == '(':
                    dp[i] = dp[i-1] + 2
                    #处理独立的括号对的情形 类似()()、()(())
                    if pre>0:
                        dp[i] += dp[pre-1]
        return max(dp);

or

1
2
3
4
5
6
7
8
9
10
11
# dp[i+1]表示前i+1个索引最长括号对
def longestValidParentheses(self, s):
    dp, stack = [0]*(len(s) + 1), []
    for i in range(len(s)):
        if s[i] == '(':
            stack.append(i)
        else:
            if stack:
                p = stack.pop()
                dp[i + 1] = dp[p] + i - p + 1 # 
    return max(dp)