题目描述
给你一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长有效(格式正确且连续)括号
子串
的长度。
样例
示例 1:
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"
示例 2:
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"
示例 3:
输入:s = ""
输出:0
性质:
1、不管如何看待括号序列,每一个左括号有唯一对应的右括号,右括号同理。
2、另“(” = 1, “)” = -1, 在匹配过程中,合法括号序列前缀和一定>=0, 如果最后总和也为0, 则匹配成功!
C++ 代码
class Solution {
public:
int work(string s)
{
int presum = 0, idx = 0, ans = 0;
for (int i = 0; i < s.size(); i ++)
{
if (s[i] == '(') presum ++;
else presum --;
if (presum == 0) ans = max(ans, i - idx + 1);
if (presum < 0) presum = 0, idx = i + 1;;
}
return ans;
}
int longestValidParentheses(string s) {
int ans = work(s); // 正着做一遍,但是无法处理左括号多的情况,比如((()), 结果是零
reverse(s.begin(), s.end()); // 反过来再做一遍可以解决,为了不重写函数,把括号序列翻转
/* 翻转之后不能直接使用work(),翻转后为))(((, 因为左右括号ASCII码分别为0x28, 0x29,
二进制最后一位与1异或即可0变1, 1变0,此时序列变为(())),可以直接work()*/
for (auto &c : s) c ^= 1;
return max(ans, work(s));
}
};