首页 > 代码库 > [LeetCode] Longest Valid Parentheses
[LeetCode] 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.
方法：用stack进行配对，用另一个对应的stack记录配对括号的下标，并把配好对的括号的起始下标记录在名为start的vector里，把对应的结束下标记录在
名为end的vector里，然后遍历两个vector，把能连接起来的括号的数量求出来。
class Solution {public: int longestValidParentheses(string s) { int num = 0; int big = 0; stack<char> st; stack<int> si; vector<int> start,end; int flag = 0; for(int i=0;i<s.size();i++){ if(st.empty()){ st.push(s[i]); si.push(i); } else if(s[i]==‘)‘ && st.top()==‘(‘){ start.push_back(si.top()); end.push_back(i); st.pop(); si.pop(); }else{ st.push(s[i]); si.push(i); } }//end for if(start.size()==0) return 0; while(start.size()>0){ int min = s.size(),minIndex=0; for(int i=0;i<start.size();i++){ if(start[i]<min){ min = start[i]; minIndex = i; } } num += (end[minIndex]-start[minIndex]+1); int theStart = end[minIndex]+1; start.erase(start.begin()+minIndex); end.erase(end.begin()+minIndex); while(find(start.begin(),start.end(),theStart) != start.end()){ vector<int>::iterator iter1,iter2; iter1 = find(start.begin(),start.end(),theStart); int d = iter1- start.begin(); iter2 = end.begin()+d; num += ((*iter2)-(*iter1)+1); theStart = (*iter2) + 1; start.erase(iter1); end.erase(iter2); }//end while if(num>big) big = num; num = 0; } return big; }//end func};
[LeetCode] Longest Valid Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。