32.md

题目地址

https://leetcode-cn.com/problems/longest-valid-parentheses/

解答1

def longestValidParentheses(s):
    """
        最长有效括号

        1.需有一个变量index记录有效括号子串的起始下标，res表示最长有效括号子串长度，初始值均为0
        2.用i作为下标遍历给字符串中的所有字符, 有两种情况, 遇到'('或者')' , 下面分别讨论这两种情况。
            2.1 遇到'(', 把'('的下标i入栈。
            2.2 遇到')', 有两种情况，栈为空，或者不为空。
                2.2.1 栈为空时，i之前的括号为无效括号，改变子串的起始位置，令index等于i+1。
                2.2.2 栈不为空时，因为只有两类括号，所以只要栈不为空，那么栈中的最后一个元素必然与右括号构成有效括号，pop出最后一个元素
                      此时栈分两种情况，为空或者不为空。
                      2.2.2.1 栈为空时，有效括号长度为当前下标i，减去有效括号的起始位置index并加1，比较有效括号长度和当前最大长度
                      2.2.2.2 栈不为空时，有效括号长度为当前下标i，减去栈中最后一个元素，比较有效括号长度和当前最大长度
    """
    res, index, stack = 0, 0, []  # 结果;
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)  # 记录索引
        elif not stack:
            index = i + 1  # 从下一位重新开始
        else:
            stack.pop()
            if stack:
                res = max(res, i - stack[-1])
            else:
                res = max(res, i - index + 1)
    return res

解答2

def longestValidParentheses(s):
    """
        最长有效括号
    """
    s = ')' + s
    dp = [0 for i in range(len(s))]
    for i, char in enumerate(s):
        if i == 0:
            continue
        if char == ')':  # 只有右括号时才可能有效
            if s[i - 1 - dp[i - 1]] == '(':  # 如果dp[i-1]范围前一个字符为左括号
                dp[i] = dp[i - 1] + 2
            dp[i] += dp[i - dp[i]]  # 加上dp[i]范围前一个字符的dp
    return max(dp)