最长有效括号

Leetcode Link: 32. 最长有效括号 - 力扣（LeetCode）

题目

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

解法一： 动态规划

思路： 理解这个动态规划的递推公式，最好尝试举几个例子

dp 五步走

1. 一维 dp，dp[i] 表示以下标 i 字符结尾的最长有效括号的长度
2. 初始化：dp[0] = 0是一定的
3. 递推公式，见下
4. 遍历方向：正常左到右
5. 举例子

关于递推公式

• 可以确定，以 '(' 结尾的子串对应的 dp 值必定为 0
• 以 ')' 结尾的子串有如下两种情况：
  • 若s[i−1]=='(' ：即 s[i] 和 s[i−1] 组成一对有效括号，有效括号长度新增 2。i 位置对最长有效括号长度为 其之前 2 个位置的最长括号长度加上当前位置新增的 2，我们无需知道 i-2 位置对字符是否可以组成有效括号对。即 $dp[i]=dp[i-2]+2$
  • 若s[i−1]==')' ：此时，如果前面有和 s[i] 组成有效括号对的字符，即形如 ( (…) )，就要求 s[i - 1] 位置 必然是有效的括号对 ，否则 s[i] 无法和前面对字符组成有效括号对。 这时，需要找到当前 s[i] 的配对位置，为 s[i-dp[i-1]-1] (举个例子画个图就知道了)，并判断该位置是不是 '('。如果不是，则当前位置 dp[i]=0，反之为 dp[i]=2+dp[i-1]+dp[i-dp[i-1]-2]

    其中，dp[i]=2+dp[i-1]表示当前这段((…))的长度，但是如果其前面也是有效的括号话，即(..)((…))，我们需要加上这一段，即再加上dp[i-dp[i-1]-2]

以上

题解：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if len(s)==0: return 0
        dp = [0]*len(s)
        for i in range(1, len(s)):
            if s[i]==')' and s[i-1] == '(':
                dp[i] = dp[i-2]+2 if i-2>=0 else 2
            # if X and 前一个是合规括号字符串(暗含s[i-1]==')') and X and 对应的配对括号是否满足要求
            if s[i]==')' and dp[i-1] > 0 and i-dp[i-1]-1>=0 and s[i-dp[i-1]-1]=='(':
                dp[i] = 2+dp[i-1]+dp[i-dp[i-1]-2] if i-dp[i-1]-2>=0 else 2+dp[i-1]
        return max(dp)  

解法二 （错误提醒）

思路：动态规划

二维不行

二维不行，开始我想的二维是考虑三种情况，即左右两个，左边两个，右边两个的括号，dp[L][R]的含义是L..R上是不是有效(True or False)，我错误的认为如果新探查的两个位置是()就一定是有效的，然而如果是((也有可能，譬如”(())(…)”此时就不能有效的判定了

基于错误的 2 维 dp 的递归公式，以此为戒！

if s[L]=="(" and s[R] == ")" and dp[L+1][R-1] is True:
    dp[L][R] = True
elif L+2<=R and s[L] == "(" and s[L+1] == ")" and dp[L+2][R] is True:
    dp[L][R] = True
elif R-2>=L and s[R] == ")" and s[R-1] == "(" and dp[L][R-2] is True:
    dp[L][R] = True

题解：

解法三 (自己的灵光乍现)

思路：一个突发奇想，我也可能解释不清楚的。 先做删除无效的括号，体会一下从解法一怎么到解法二

易知，可以通过 score 指示当前的括号字符串是不是合规的，有

• score < 0 一定违规
• score = 0 一定合规
• score > 0 有可能有一部分合规

为什么 score > 0 不一定合规？ 假设我们按照删除无效的括号中，遇到 (，score+1，遇到 ） 分情况处理。显然，对于 (()，我们的 score 一直都大于 0，此时是有合规的部分的，但是我们 score 一直不等于 0，找不到。

那咋办？

逆序！再来！想想为啥我们 score 一直不等于 0，因为代表-1 的括号数量不够。正常情况下，先左再右；逆序之后，匹配的顺序就是先右再左了，此时遇到 ) 时 score+1，反之分情况。

我们可以用一个 cnt 变量指示当前合规的有多长，一旦遇到 score==0还需要score-1 的情况，就知道只有 cnt 这么长合规，下面就开启新的合规统计。

然而，有两个细节：

1. for 循环遍历完之后，如果恰好 score==0，此时循环体里的判定是走不到的，所以 for 外面我们要判断一下
2. )()()( 这种输入，无论正走反走，都不会遇到score==0还需要减一的情况，但是会出现合规的score==0，所以在每个for的开始我们都要判定一下。

题解：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        cnt = 0  # 当前合规长度计数
        res = -float('inf') # 初始化
        score = 0
 
        for c in s:
		    # 对应细节2
            res = max(res, cnt) if score == 0 else res
            if c == "(":
                score += 1
                cnt += 1
            else:
                if score > 0:
                    cnt += 1
                    score -= 1
                else:
                    res = max(res, cnt)
                    score = 0
                    cnt = 0
        # 对应细节1
        res = max(res, cnt) if score == 0 else res
        s = s[::-1]
        score = 0
        cnt = 0
        for c in s:
            res = max(res, cnt) if score == 0 else res
            if c == ")":
                score += 1
                cnt += 1
            else:
                if score > 0:
                    score -= 1
                    cnt += 1
                else:
                    res = max(res, cnt)
                    score = 0
                    cnt = 0
        res = max(res, cnt) if score == 0 else res
        return res

解法四：栈 (参考的，很巧)

思路 对于这种括号匹配问题，一般都是使用栈

我们先找到所有可以匹配的索引号，然后找出最长连续数列！

例如：s = ')(()())'，我们用栈可以找到，

位置 2 和位置 3 匹配， 位置 4 和位置 5 匹配， 位置 1 和位置 6 匹配，

这个数组为：2,3,4,5,1,6 这是通过栈找到的，我们按递增排序！1,2,3,4,5,6

找出该数组的最长连续数列的长度就是最长有效括号长度！

所以时间复杂度来自排序：$O(nlogn)$。

题解

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [] # 栈
        ind = []  # 记录有效的成对索引
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            else:
                if len(stack) != 0:
                    ind.append(stack.pop())
                    ind.append(i)
                else:
                    continue
        ind.sort()
 
        cnt = 1
        res = -float('inf')
        # 寻找最长连续子串长度
        for i in range(1, len(ind)):
            if ind[i] - ind[i-1] >= 2:
                res = max(res, cnt)
                cnt = 1
            else:
                cnt += 1
        res = max(res, cnt)
 
        # 当 res == 1 说明为空，因为不可能只有一个括号。提前令cnt=1是为了减少判断
        return 0 if res == 1 else res 

启发和联系