最长有效括号 - etherwindy

689 words

3 minutes

最长有效括号

2024-04-20

LeetCode

Algorithms

/

Dynamic Programming

Cover Image Source: Source

题目链接：32. 最长有效括号

误入歧途#

本题一眼顶真，鉴定为动态规划，关键在于怎么动态规划。

一开始我的想法比较暴力，用一个二维数组f[n][n+1]来保存状态（实际用向量来实现）。其中f[i][j]表示从 $[i, j)$ 范围内的连续子串是否满足括号匹配规则（ $i=j$ 时表示空串，此时f[i][j]值为true）。

对于一个合法的子串，一定以')'结尾。故合法子串可表示为 $A(B)$ ，A和B均可为空串。对于每一个满足上式的子串，只需遍历所有的有序对 $(A, B)$ 即可判断是否是合法子串。转移方程如下：

f[i][j]= \left\{ \begin{aligned} &1, & \sum_{k\in[i, j-1), s[i+k]='('}f[i][k]f[i+k+1][j] \neq 0, \\ &0, & otherwise. \end{aligned} \right.

代码如下

1
class Solution {
2
public:
3
    int longestValidParentheses(string s) {
4
        int n = s.length();
5
        int maxn = 0;
6
        vector<vector<int>> f(n, vector<int>(n + 1, 0));
7
        for (int i = 0; i < n; ++i) f[i][0] = 1;
8
        for (int j = 2; j <= n; j+=2)
9
            for (int i = 0; i + j <= n; ++i)
10
                if (s[i + j - 1] == ')')
11
                    for (int k = 0; k < j - 1; k+=2)
12
                        if (s[i + k] == '(' && f[i][k] && f[i + k + 1][j - k - 2]) {
13
                            f[i][j] = true;
14
                            maxn = j;
15
                            break;
16
                        }
17
        return maxn;
18
    }
19
};

时间复杂度为 $O(N^3)$ 。很不幸的是这个方法超时了。

另起炉灶#

重新思考后，我尝试了新的算法，将时间复杂度降到了 $O(N)$ 。新的算法用一维数组dp[n+1]保存状态。其中dp[i]表示所有以第 $i-1$ 个字符为结尾的合法子串中最长的子串的第一个字符的下标，即下标在 $[dp[i], i)$ 中的所有字符组成一个合法子串且该子串无法向左扩充为新的子串。如果没有这样的子串，则 $dp[i] = i$ 。

沿用之前的思路，合法子串可表示为 $A(B)$ 。当s[i-1]为')'时，通过dp[i-1]可获取 $B$ ，若s[dp[i-1]-1]为'('，则通过dp[dp[i-1]-1]可获取 $A$ 。转移方程如下：

dp[i] = \left\{ \begin{aligned} & dp[dp[i-1]-1], & s[i-1]=')',\ dp[i-1]\neq 0,\ [dp[i-1]-1]='(', \\ & i, & otherwise. \end{aligned} \right.

代码如下：

1
class Solution {
2
public:
3
    int longestValidParentheses(string s) {
4
        int n = s.length();
5
        int maxn = 0;
6
        vector<int> dp(n + 1, 0); // dp[i]表示所有以第i-1个字符为结尾的合法子串中最长的子串的第一个字符的下标
7
        for (int i = 0; i <= n; ++i) dp[i] = i;
8
        for (int i = 2; i <= n; ++i) {
9
            if (s[i - 1] != ')') continue;
10
            if (dp[i - 1] == 0 || s[dp[i - 1] - 1] != '(') continue;
11
            dp[i] = dp[dp[i - 1] - 1];
12
            maxn = max(i - dp[i], maxn);
13
        }
14
        return maxn;
15
    }
16
};