思路一:
首先从最基本的问题说起,遍历整个字符串,遍历到当前字符,我们计算以此字符为结束的括号匹配最长序列为多长,可以从当前字符到前面的所有字符组成字符串来进行判断,计算最终的结果是否比当前记录的结果长。等到遍历了所有的字符,也就知道这个字符中可匹配的括号序列的最大长度。
int check(string& str,int begin,int end) { stack<char> st; int i; for(i = begin;i<=end;i++) { if(str[i] ==')' &&(!st.empty() && st.top() =='(')) st.pop(); else st.push(str[i]); } if(st.empty()) return end-begin+1; else return 0; } //也可以这么理解数列和为0的最长的序列 int Longest_dp(string& str) { int i,j; int tmp; int max=0; int pos; for(i=0;i<str.size();i++) { for(j=0;j<=i;j++) if((tmp = check(str,j,i))>max) { max = tmp; break; } } return max; }
int longestValidParentheses(string s) { bool *a = new bool[s.length()]; memset(a, false, s.length()); stack<int> st; for (int i = 0; i < s.length(); ++i) { if (s[i] == '(') { st.push(i); } else if (s[i] == ')' && !st.empty()) { a[i] = true; a[st.top()] = true; st.pop(); } } int max_len = 0, cur_len = 0; for (int i = 0; i < s.length(); ++i) { if (a[i]) ++cur_len; else cur_len = 0; max_len = max(max_len, cur_len); } return max_len; }思路三:
如果我们使用栈记录某一个符号的在字符串的位置,假如对于当前字符和栈顶位置的字符可以匹配的,那么可以根据栈是否为空来判断当前最长匹配子序列,然后和目标进行比较。
int longestValidParentheses(string s) { stack<int> st; int pos; int maxlen = 0; for(int i = 0 ; i < s.size() ; i++) { if(s[i] == '(') st.push(i); else // ')' { if(!st.empty() && s[st.top()]=='(') { st.pop(); if(st.empty()) pos = i+1; else pos = i-st.top(); if(maxlen < pos) maxlen = pos; } else st.push(i); } } return maxlen; }
leetcode| longest valid parentheses最长括号可匹配序列
原文:http://blog.csdn.net/yusiguyuan/article/details/44623345