题目描述
给定一个只包含 '('
和 ')'
的字符串,找出最长的包含有效括号的子串的长度。
样例1
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
样例2
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
算法1
(线性扫描) $O(n)$
首先括号序列有两个很重要的性质,第一个是对于一个合法的序列,每一个右括号所对应的左括号是唯一确定的。另一个性质是括号序列合法等价于括号序列的所有前缀和大于等于0,且总和等于0,这里让左括号等于1,右括号等于-1。
我们可以先从左往右扫描一遍序列,维护一个cnt
变量,当它小于0的时候说明我们遇到了一个无法被匹配的右括号,根据性质一我们得到前面的序列中也没有多余的左括号可以给它匹配,即[j, i]
的子串不合法,这时我们将j
更新为i + 1
并且将cnt
置0。
但是从左往右做只能适用于左括号的数量小于等于右括号数量的时候,比如对"(((())"
我们就无法统计到正确答案。这时候我们可以从右往左再扫一遍,并且我们将左右括号的地位对调,即左括号等于-1,右括号等于1,这样就可以得到左括号数量大于右括号数量时的答案了。
C++ 代码
class Solution {
public:
int longestValidParentheses(string s) {
int cnt = 0;
int res = 0;
for (int i = 0, j = 0; i < s.size(); i ++ )
{
if (s[i] == ')') cnt -- ;
else cnt ++ ;
if (cnt == 0) res = max(res, i - j + 1);
else if (cnt < 0) j = i + 1, cnt = 0;
}
cnt = 0;
for (int i = s.size() - 1, j = s.size() - 1; i >= 0; i -- )
{
if (s[i] == '(') cnt -- ;
else cnt ++ ;
if (cnt == 0) res = max(res, j - i + 1);
else if (cnt < 0) j = i - 1, cnt = 0;
}
return res;
}
};
算法2
(动态规划) $O(n)$
dp[i]
状态定义为以第i
个字符结尾的最长合法括号序列的长度,这样答案为max(dp[1],...,dp[n])
。接下来我们考虑状态怎么转移:
s[i] == ')'
并且s[i - 1] == '('
,那么dp[i] = dp[i - 2] + 2
。s[i] == ')'
并且s[i - 1] == ')'
,那么在i - 1
的位置有长为dp[i - 1]
的合法序列,如果这个序列的前一个位置即s[i - dp[i - 1] - 1]
为左括号'('
,那么根据性质一它就可以和s[i]
的右括号进行配对,并且我们可以加上之前的合法括号序列dp[i - dp[i - 1] - 2]
。
这里为了方便处理我们让dp
数组的下标从1开始方便处理边界,即dp[1]
代表了以 s[0]
为结尾的最长合法序列。
C++ 代码
class Solution {
public:
int longestValidParentheses(string s) {
if (s.empty()) return 0;
vector<int> dp(s.size() + 1, 0);
int res = 0;
for (int i = 2; i <= s.size(); i ++ )
{
if (s[i - 1] == ')')
{
if (s[i - 2] == '(')
dp[i] = dp[i - 2] + 2;
else if (i - dp[i - 1] - 1 > 0 && s[i - dp[i - 1] - 2] == '(' )
dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
res = max(res, dp[i]);
}
}
return res;
}
};
算法3
(栈) $O(n)$
括号序列匹配的过程可以用栈来模拟,不过这里由于要记录长度所以我们在栈中存入下标。
首先我们遇见左括号的时候可以直接入栈,遇见右括号时需要看栈顶来找到和它匹配的左括号:
- 如果栈顶没有能和它匹配的左括号(栈为空或者栈顶是右括号),说明该右括号无法被匹配,那么它可以被压入栈中来当做下一个新序列的起点位置。
- 如果栈顶有可以和它匹配的左括号,我们就让他们匹配,然后计算当前序列的长度。此时序列要么是从头开始要么是从上一个无法被匹配的右括号开始。
C++ 代码
class Solution {
public:
int longestValidParentheses(string s) {
int res = 0, n = s.length();
stack<int> st;
for(int i = 0 ; i < n ; i ++)
{
if(s[i] == '(') st.push(i);
else
{
if (st.empty() || s[st.top()] == ')') st.push(i);
else
{
st.pop();
res = max(res, st.empty() ? i + 1 : i - st.top());
}
}
}
return res;
}
};