LeetCode 32. 最长有效括号

◎

本节目标

记录以右端点结尾的有效长度，并把匹配括号前的区间拼接起来。

这是序列与字符串动态规划中末尾区间拼接的母题。

题意与约束

给定只含左右括号的字符串，求最长连续有效括号子串的长度。

第一反应与重复子问题

有效片段必须以右括号收尾；若前一个位置已有有效片段，应跳过它找到与当前右括号配对的左括号，并可能连接更早片段。

状态定义与转移推导

令 dp[i] 为以 i 为右端点的最长有效长度。相邻 () 时接上 dp[i-2]；前一位为 ) 时，令 left=i-dp[i-1]-1，若为 (，则拼成 dp[i-1]+2+dp[left-1]。

正确性依据

两种转移分别穷尽当前右括号与相邻左括号匹配，或跨过前一有效段匹配的情形；第二种再加上匹配左括号前的状态，正好完成区间拼接。

样例执行过程

在 ()(()) 中，末尾右括号跨过中间的 () 找到开头左括号，并接上前段，得到长度 6。

代码实现

C++

C++17

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> length(s.size(), 0);
        int answer = 0;
        for (int right = 1; right < static_cast<int>(s.size()); right++) {
            if (s[right] != ')') {
                continue;
            }
            if (s[right - 1] == '(') {
                length[right] = 2 + (right >= 2 ? length[right - 2] : 0);
            } else {
                int left = right - length[right - 1] - 1;
                if (left >= 0 && s[left] == '(') {
                    length[right] = length[right - 1] + 2 + (left >= 1 ? length[left - 1] : 0);
                }
            }
            answer = max(answer, length[right]);
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        lengths = [0] * len(s)
        answer = 0
        for right in range(1, len(s)):
            if s[right] != ')':
                continue
            if s[right - 1] == '(':
                lengths[right] = 2 + (lengths[right - 2] if right >= 2 else 0)
            else:
                left = right - lengths[right - 1] - 1
                if left >= 0 and s[left] == '(':
                    lengths[right] = lengths[right - 1] + 2 + (lengths[left - 1] if left >= 1 else 0)
            answer = max(answer, lengths[right])
        return answer

复杂度分析

一次扫描，时间 O(n)，状态数组空间 O(n)。

边界与易错点

• 空串答案为零。
• 计算 left 后必须检查非负，且拼接 dp[left-1] 前检查下标。

模式迁移

当匹配符号可嵌套且答案要求连续区间时，可考虑记录“以右端点结尾”的长度或可行性。