Leetcode之Longest Valid Parentheses
Leetcode之Longest Valid Parentheses
forrestlin
发布于 2018-05-24 10:58:42
发布于 2018-05-24 10:58:42
好久没来更新Leetcode题目了，因为之前都去刷lintcode了，结果发现还是leetcode是我的本命啊~~
第二次刷leetcode，感触良多，有些题目以前不会现在会了，但是有些以前明明会的，现在反而想很久，还有可能需要看提示，而且复杂度还比以前的高了，感觉人变笨了
，肯定因为很久没来更新博客的原因。嗯，所以今天就讲一讲Longest Valid Parentheses这道题吧。
今天重新做这道题时，一开始想得太简单了，没考虑需要连续的子串，导致一开始的O(n)做法出错了，然后偷瞄了一下提示，动规，好吧，一开始也有想过，但是没细想进去，重新想了一下，确实可以做，递推公式如下：
代码如下：
int longestValidParentheses(string s) {
int len = s.length();
vector<int> dp(len + 1, 0);
for (int i = 0; i < len; i++) {
int count = 0;
for (int k = i; k >= 0; k--) {
if (s[k] == ')') {
count++;
} else {
count--;
if (count == 0) {
dp[i + 1] = max(dp[i + 1], dp[k] + i - k + 1);
} else if (count < 0) {
break;
}
}
}
if (i - dp[i] - 1 >= 0 && s[i - dp[i] - 1] == '(' && s[i] == ')')
dp[i + 1] = max(dp[i] + 2, dp[i + 1]);
}
return *max_element(dp.begin(), dp.end());
}另一种做法是，用一个栈保存已经遍历过的左括号，然后求出所有左括号是否都有匹配，最后遍历左括号数组，将连续的左括号的长度相加，遇到0就重新算，得到最长长度。这样的复杂度确实就是O(n)，佩服以前的我。
class Solution {
public:
struct Letter{
char val;
int index;
Letter(char v,int i):val(v),index(i){};
};
int longestValidParentheses(string s) {
int result=0,max=0;
stack<Letter> letterStack;
vector<int> letterCount;
for(int i=0;i<s.length();i++){
if(s[i]==')'&&letterStack.size()==0){
letterCount.push_back(0);
continue;
}else if(s[i]=='('){
letterStack.push(Letter(s[i],letterCount.size()));
letterCount.push_back(0);
}else{
Letter topLetter=letterStack.top();
letterCount[topLetter.index]+=2;
letterStack.pop();
}
}
for(int i=0;i<letterCount.size();i++){
if(letterCount[i]==0){
if(max>result){
result=max;
}
max=0;
}else{
max+=letterCount[i];
}
}
if(max>result)
result=max;
return result;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016年09月27日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读