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.

C++:
01 class Solution {
02 public:
03     int longestValidParentheses(string s) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int result=0;
07         int tmp=0;
08         int n=s.size();
09         stack<int> A;
10         for(int i=0;i<n;i++)
11         {
12             if(s[i]==‘(‘)
13             {
14                 if(tmp!=-1)
15                 {
16                     A.push(tmp);
17                     tmp=-1;
18                 }
19                 else
20                 {
21                     A.push(i);
22                 }
23             }
24             else if(s[i]==‘)’)
25             {
26                 if(A.empty())
27                 {
28                     tmp=-1;
29                 }
30                 else
31                 {
32                     tmp=A.top();
33                     A.pop();
34                     if(result<itmp+1)
35                         result=itmp+1;
36                 }
37             }
38         }
39         return result;
40     }
41 };
Advertisements
This entry was posted in Array and linked list, Stack and Queue, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s