32-最长有效括号

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

解法

利用栈

思路：

特判，若s为空，返回0
初试化栈stack=[-1]，和结果res=0。栈中元素表示上一不匹配位置索引。
遍历s：
- 若s[i]=="("，将当前位置索引加入stack。表示将当前左括号需要匹配，为不匹配索引。
- 若s[i]==")"：
  出栈，stack.pop()。表示将对应左括号索引出栈，或者当栈中只有 ) 时，将上一 ) 索引出栈。
  若栈为空，表示之前的所有的 ( 匹配成功，上一步出栈的是栈底的-1或者是前一个不匹配的 ) 。则更新栈底为当前 ) 的索引，表示不匹配的位置。
- 否则，说明和栈中的 ( 匹配上了，此时更新最长序列res=max(res,i−stack[−1])。表示当前位置索引减去上一不匹配位置索引和之前res中的较大值。
更新res

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0
        res = 0
        stack = [-1]  # -1占位
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            elif s[i] == ")":
                stack.pop()  # 弹出对应的左括号索引
                # 空栈表示已经出现不合法的括号，
                # 把索引值压进栈中
                if not stack:
                    stack.append(i)
                else:
                    # i-stack中倒数第一个的索引值
                    # 为当前合法的长度大小
                    res = max(res, i - stack[-1])
        return res

动态规划

思路：

特判，若s为空，返回0
初试化dp=[0,...,0]，长度为n。dp[i]表示到i位置的最长有效括号的长度。
显然，当s[i]==(时，dp[i]=0
遍历字符串，遍历区间[1,n)：
- 当s[i]==)时，若s[i−1]==(，说明这两个有效。则dp[i]=dp[i-2]+2
  否则s[i-1]==)，此时找到上一匹配字符串的上一位i−dp[i−1]−1：
- 若s[i-dp[i-1]-1]==(，说明s[i]s[i]可以和s[i-dp[i-1]-1]匹配：则dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2，表示当前位置的最长有效括号长度等于上一位有效括号的长度加上自身匹配的上一位的有效括号的长度加上2。
更新res，res=max(res,dp[i])

# 动态规划
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if(not s):
            return 0
        res = 0
        n = len(s)
        dp = [0]*n
        for i in range(1, len(s)):
            if(s[i] == ")"):
                if(s[i-1] == "("):
                    dp[i] = dp[i-2]+2
                if(s[i-1] == ")" and i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == "("):
                    dp[i] = dp[i-1]+dp[i-dp[i-1]-2]+2
                res = max(res, dp[i])
        return res

来源

LeetCode中该题地址，Click here!