【Python】32. 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，用栈：1.遍历字符串，当遇到'('的时候，把其索引放入堆栈，当遇到')'时候，如果栈顶是'('，则出栈操作一次，否则索引入栈
2.当栈为空时候，说明字符串全体合法，返回字符串长度
3.如果栈不为空，则比较栈中相邻索引的“空洞”长度，最长的空洞即为所求
class Solution {
public:
int longestValidParentheses(string s) {
int n=s.length(),i,longest=;
stack<int> st;
for(i=;i<n;i++){
if('('==s[i])
st.push(i);
else{
if(!st.empty()){
if(s[st.top()]=='(')
st.pop();
else
st.push(i);
}
else{
st.push(i);
}
}
}
if(st.empty()) longest = n;
else{
int rear=n,front=;
while(!st.empty()){
front=st.top();
st.pop();
longest = max(longest,rear--front);
rear = front;
}
longest = max(longest,front);
}
return longest;
}
};
思路2：动态规划
用longest[]记录字符串中截至每个位置时的最长合法字符串长度
如果s[i]为'('，那么longest[i]为0，因为左右以'('结尾的字符串肯定不合法，为0
如果s[i]为')'，那么分两种情况
1.当s[i-1]为'('时候， longest[i] = longest[i-2] + 2
2.当s[i-1]为')'，和s[i-longest[i-1]-1] == '('时，longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]；
longest[i-longest[i-1]-2]代表上一个以')'结尾的合法字符串
class Solution {
public:
int longestValidParentheses(string s) {
int len=s.length();
if(len<=)
return ;
int curmax=;
vector<int> longest(len,);
for(int i=;i<len;i++){
if(')'==s[i]){
if('('==s[i-]){
longest[i]=(i->?longest[i-]+:);
curmax=max(longest[i],curmax);
}
else{
if(i-longest[i-]->=&&s[i-longest[i-]-]=='('){
longest[i]=longest[i-]++(i-longest[i-]->?longest[i-longest[i-]-]:);
curmax=max(longest[i],curmax);
}
}
}
}
return curmax;
}
};
最新文章
- 基于Metronic的Bootstrap开发框架经验总结（5）--Bootstrap文件上传插件File Input的使用
- SecWeek
- 腾讯OAuth授权联合登录
- selenium操作滚动条方法
- [Chapter 3 Process]Practice 3.8: Describe the differences among short-term, medium-term, long-term scheduling
- create mystic by Django
- 基于IHttpAsyncHandler的UDP收发器
- c# 改变图片的大小（w,h）
- 使用ffmpeg快速生成视频截图
- Oracle Exadata体系笔记
- Linux 查看 80 端口的占用情况
- Ubuntu14.04搭建安装svnserver
- Javascript语言精粹之正则表达式知识整理
- 区分内边距与外边距padding和margin
- [转]Top 10 DTrace scripts for Mac OS X
- 认识Java（2）
- 【原创】详细案例解剖——浅谈Redis缓存的常用5种方式（String，Hash，List，set，SetSorted ）
- appium api笔记
- git bash + gitee
- 2017-2018-2 20165237 实验四《Android开发基础》实验报告