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.

Solution: using a stack to match the '(' and ')' pairs, and use a hashtable to store these pairs. later, given a left parentheses, with the help of the hash table, you can find the furthest match ')' parentheses.

Java语言: LongestValidParentheses

01 public int longestValidParentheses(String s) {
02     //store the left parentheses
03     Stack<Integer> st=new Stack<Integer>();
04     //store the left, right pairs of parentheses
05     Hashtable<Integer, Integer> matches=new Hashtable<Integer,Integer>();
06     int length=0;
07     int max=0;
08     for(int i=0;i<s.length();i++)
09     {
10         if(s.charAt(i)=='(' )
11         {
12             st.push(i);
13         }
14         if(s.charAt(i)==')')
15         {
16             if(st.size()==0)
17             {
18                 continue;
19             }
20             else
21             {
22                 int left=st.pop();
23                 matches.put(left,i);
24             }
25         }
26     }
27   
28     for(int i=0;i<s.length();i++)
29     {
30         if(matches.containsKey(i))
31         {
32             int value=matches.get(i);
33             while(matches.containsKey(value+1))
34             {
35                 value=matches.get(value+1);
36             }
37             length=value-i+1;
38             if(length>max)
39             {
40                 max=length;
41             }
42         }
43     }
44   
45     return max;
46 }