Given a string containing just the characters '('
and ')'
, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
给定一个只包含 '('
和 ')'
的字符串,找出最长的包含有效括号的子串的长度。
因为求得是最长有效括号的子串的长度,子串有效的话,其长度一定是偶数;我们可以遍历每种偶数长度的子串,针对每种可能判断是否是有效的,如果有效,求子串的最大长度。具体步骤:
class Solution {
public:
int longestValidParentheses(string s) {
int maxlen = 0;
for (int i=0; i< s.size(); i++){
for (int j=i+2; j<= s.size(); j += 2){
if (isValid(s.substr(i, j-i))){
maxlen = max(maxlen, j-i);
}
}
}
return maxlen;
}
bool isValid(string s){
stack<char> data;
for (char c: s){
if (c == '(')
data.push(c);
else if (!data.empty() && data.top() == '(')
data.pop();
else
return false;
}
return data.empty();
}
};
但是由于时间复杂度太高O(N**3),导致超时。
但是其中括号有效性判断,还是可以学习的,使用栈数据结构辅助判断。
将上面的有效性判断方法稍加修改:使用一个变量记录子串的起始位置,同时入栈时,把字符所在的下标入栈,而不是字符‘(’,‘)’,使用下标运算记录子串
完整代码:
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> data;
int result = 0, start = 0;
for (int i=0; i< s.size(); i++){
if (s[i] == '(')
data.push(i);
else{
if (data.empty())
start = i+1;
else{
data.pop();
result = data.empty() ? max(result, i-start+1) : max(result, i- data.top());
}
}
}
return result;
}
};
状态:DP[i]:以s[i-1]结尾的最长的包含有效括号的子串的长度。
通项公式:
s[i] = ‘(’, DP[i] = 0;
s[i] = ‘)’: 此时需要向前看,先确定dp[i-1]的长度,可能有(())连续对的存在,所以找到字符i-dp[i-1]-2,如果这个字符为左括号,那么有效长度+2;但是还可能存在"()(())"情况,也就是说找到对应前缀后前面还有有效长度,此时它的有效长度记录在dp[i-dp[i-1]-2]中,所以dp[i] = dp[i-1]+2+dp[i-dp[i-1]-2]
,这种情况是,有效对+(有效对),当计算最后一个右括号时,需要找到对应的左括号,但是dp[左括号]也可能不为0,所以此时需要再加上dp[左括号]的值。dp[i]表示以s[i-1]结尾的最长有效子串长度,为了避免取dp[i-1]时越界
代码:
class Solution {
public:
int longestValidParentheses(string s) {
int res = 0, n = s.size();
vector<int> dp(n + 1);
for (int i = 1; i <= n; ++i) {
int j = i - 2 - dp[i - 1];
if (s[i - 1] == '(' || j < 0 || s[j] == ')') {
dp[i] = 0;
} else {
dp[i] = dp[i - 1] + 2 + dp[j];
res = max(res, dp[i]);
}
}
return res;
}
};
https://www.cnblogs.com/grandyang/p/4424731.html
https://bangbingsyb.blogspot.com/2014/11/leetcode-longest-valid-parentheses.html