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.
思路：
栈的经典应用
我的代码：
public class Solution { public int longestValidParentheses(String s) { if(s==null || s.length()==0) return 0; Stack<Integer> stack = new Stack<Integer>(); int max = 0; for(int i=0; i<s.length(); i++) { if(stack.isEmpty() || s.charAt(stack.peek())==‘)‘ || s.charAt(i)==‘(‘) stack.push(i); else { stack.pop(); int index = stack.isEmpty()? -1 : stack.peek(); max = Math.max(max,i-index); } } return max; } }
他人代码：
public int longestValidParentheses(String s) { char[] S = s.toCharArray(); int[] V = new int[S.length]; int open = 0; int max = 0; for (int i=0; i<S.length; i++) { if (S[i] == ‘(‘) open++; if (S[i] == ‘)‘ && open > 0) { V[i] = 2 + V[i-1] + (i-2-V[i-1] > 0 ? V[i-2-V[i-1]] : 0); open--; } if (V[i] > max) max = V[i]; } return max; }
学习之处：
原文：http://www.cnblogs.com/sunshisonghit/p/4493853.html
