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
» Solve this problem")()())"
, where the longest valid parentheses substring is "()()"
, which has length = 4.[Thoughts]
维护一个栈,每次维护上一个可能的左边际。
[Code]
1: int longestValidParentheses(string s) {
2: const char* str = s.c_str();
3: int nMax=0;
4: const char *p = str;
5: vector<const char*> sta;
6: while(*p !='\0')
7: {
8: if(*p == '(')
9: {
10: sta.push_back(p);
11: }
12: else
13: {
14: if(!sta.empty() && *sta.back()=='(')
15: {
16: sta.pop_back();
17: nMax = max(nMax, p-(sta.empty()?str-1:sta.back()));
18: }
19: else
20: {
21: sta.push_back(p);
22: }
23: }
24: p++;
25: }
26: return nMax;
27: }
No comments:
Post a Comment