最长有效括号

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

  • 示例 1：

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

  • 示例 2：

    输入：s = “)()())”
    输出：4
    解释：最长有效括号子串是 “()()”

  • 示例 3：

    输入：s = “”
    输出：0

提示：

  • 0 <= s.length <= 3 * 104
  • s[i] 为 ‘(‘ 或 ‘)’

Solution

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        if (s.empty()) {
            return 0;
        }
        int longest = 0;
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            if (s.at(i) == '(') {
                int count = 1;
                int vc = 1;
                for (int j = i + 1; j < len; ++j) {
                    if (count == 0 && s.at(j) == ')') {
                        vc = 0;
                        continue;
                    }
                    if (s.at(j) == '(') {
                        count = count + 1;
                    } else {
                        count = count - 1;
                    }
                    vc++;
                    if (count == 0 && vc > longest) {
                        longest = vc;
                    }
                }
            }
        }
        return longest;
    }
};


int main() {
    std::cout << Solution().longestValidParentheses("(()") << std::endl; // 2
    std::cout << Solution().longestValidParentheses(")()())") << std::endl; // 4
    std::cout << Solution().longestValidParentheses(")()())()()(") << std::endl; // 4
    
    return 0;
}