## Sunday, March 10, 2013

### [LeetCode] Longest Valid Parentheses, Solution

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.
» Solve this problem

[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:       }
``````