最长有效括号子串问题

题目描述
给定一个只包含字符'('和')'的字符串s，找出最长有效（格式正确）括号子串的长度。

有效括号字符串需满足：

• 空字符串是有效的
• 如果A和B是有效的，那么AB也是有效的
• 如果A是有效的，那么(A)也是有效的

解题思路
这个问题可以使用动态规划来解决。我们定义dp[i]表示以第i个字符结尾的最长有效括号子串的长度。

详细解题步骤

步骤1：定义状态

• dp[i]：表示以s[i]结尾的最长有效括号子串的长度
• 初始化所有dp[i] = 0

步骤2：分析状态转移
对于每个位置i（从1开始遍历）：

1. 如果s[i] == '('，那么以'('结尾不可能是有效括号，dp[i] = 0
2. 如果s[i] == ')'，需要分情况讨论：
   • 情况1：s[i-1] == '('
     • 形如"...()"，那么dp[i] = dp[i-2] + 2
   • 情况2：s[i-1] == ')'
     • 形如"...))"，需要检查与当前')'匹配的'('位置
     • 如果i-dp[i-1]-1 >= 0且s[i-dp[i-1]-1] == '('
     • 那么dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]

步骤3：边界条件处理

• 当i=0时，单独处理
• 注意数组越界检查

步骤4：算法实现

def longestValidParentheses(s):
    if not s:
        return 0
    
    n = len(s)
    dp = [0] * n
    max_len = 0
    
    for i in range(1, n):
        if s[i] == ')':
            # 情况1：前一个字符是'('
            if s[i-1] == '(':
                dp[i] = (dp[i-2] if i >= 2 else 0) + 2
            # 情况2：前一个字符是')'，且存在匹配的'('
            elif i - dp[i-1] > 0 and s[i-dp[i-1]-1] == '(':
                dp[i] = dp[i-1] + 2
                # 加上前面可能存在的有效括号长度
                if i - dp[i-1] - 2 >= 0:
                    dp[i] += dp[i-dp[i-1]-2]
            
            max_len = max(max_len, dp[i])
    
    return max_len

步骤5：示例分析
以字符串"()(())"为例：

• i=0: s[0]='('，dp[0]=0
• i=1: s[1]=')'，且s[0]='('，dp[1]=dp[-1]+2=0+2=2
• i=2: s[2]='('，dp[2]=0
• i=3: s[3]='('，dp[3]=0
• i=4: s[4]=')'，且s[3]='('，dp[4]=dp[2]+2=0+2=2
• i=5: s[5]=')'，检查i-dp[4]-1=5-2-1=2，s[2]='('，匹配成功
  dp[5]=dp[4]+2+dp[1]=2+2+2=6

步骤6：复杂度分析

• 时间复杂度：O(n)，只需遍历一次字符串
• 空间复杂度：O(n)，用于存储dp数组

步骤7：优化思路
可以使用栈来模拟括号匹配过程，记录有效括号的起始位置，也能在O(n)时间内解决问题，且空间复杂度可以优化到O(1)。