[LeetCode] Longest Valid Parentheses


Longest Valid Parentheses

Given a string containing just the characters '(' and ')',
find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()",
which has length = 2.

Another example is ")()())", where the longest valid parentheses substring
is "()()", which has length = 4.

解题思路:

题意找到最长有效括号的子串长度。求最大问题,第1想法就是动态计划,但是,通项公式真不好找。喜刷刷http://bangbingsyb.blogspot.jp/2014/11/leetcode-longest-valid-parentheses.html中有相干说明,我没有理解,大哭

由因而括号问题,可以用栈来实现。这跟判断栈是不是有效不同。注意到,若某个右括号不与前面的某个左括号匹配,那末,这个右括号可以作为子串分割标记。大体思想是,若遇到左括号,无条件将左括号的下标入栈。若遇到右括号,若栈顶是左括号与之匹配,将左括号出栈,更新最大的长度值。若栈顶没有左括号与之匹配,将该右括号的下标入栈,作为分割字符。代码以下:

class Solution {
public:
int longestValidParentheses(string s) {
int len=s.length();

stack<int> st;

int maxLen=0;

for(int i=0; i<len; i++){
if(s[i]=='('){
st.push(i);
}else{
if(!st.empty()&&s[st.top()]=='('){
st.pop();
maxLen = max(maxLen, st.empty()?i+1:i-st.top());
}else{
st.push(i);
}
}
}

return maxLen;
}
};

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » [LeetCode] Longest Valid Parentheses

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡