leetcode32.最长有效括号

Posted on | In |
Words count in article: 354 | Reading time ≈ 1

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

示例：

1
2
3
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

分析：

1
2
3
4
5
状态表示：
	设 f(i)为以i为结尾的最长合法子串。
	初始时，f(0)=0。
状态计算：
    转移时，我们仅考虑当前字符是 ) 的时候。如果上一个字符是 (，即 ...() 结尾的情况，则 f(i)=f(i−1)+2。如果上一个字符是 )，即 ...)) 的情况，则我们通过上一个字符的动规结果，判断是否能匹配末尾的 )。判断 s[i - f(i - 1) - 1] 是 (，即 ...((合法))，则可以转移 f(i)=f(i−1)+2+f(i−f(i−1)−2)。最终答案为动规数组中的最大值。

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> f(n, 0);

        for (int i = 1;i < n;i ++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    if (i >= 2) f[i] = f[i - 2] + 2;
                    else f[i] = 2;
                } else {
                    if (i - f[i - 1] - 1 >= 0 && s[i - f[i - 1] - 1] =='(')
                        if (i - f[i - 1]- 2 >= 0)
                            f[i] = f[i - 1] + 2 + f[i - f[i - 1] - 2];
                        else 
                            f[i] = f[i - 1] + 2;
                }
            }
        }

        int res = 0;
        for (int i = 0;i < n;i ++)
            res = max(res, f[i]);

        return res;
    }
};

[原题链接](32. 最长有效括号 - 力扣（Leetcode）)

0%