Longest Valid Parentheses @LeetCode

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.

	package leetcode.string;
	import java.util.Stack;
	/**
	* Solution: 判断 ')' 的情况, 挺麻烦的一道题，考虑corner比较多，只需要循环一边 O(n).
	* 这题目麻烦的地方在于在碰到')'时候如何判断合法序列. 另外用stack 存index值，很关键
	* 1. stack isEmpty --> 当前 ')' 无合法序列, 更新start, 只有inValid才更新start
	* 2. stack !isEmpty, pop()
	* * isEmpty like (), (() ) --> length = index-start+1
	* * !isEmpty like (() --> length = index-stack.peek(); 这里就不能用start 标记了
	*
	* Reference: http://codeganker.blogspot.com/2014/03/longest-valid-parentheses-leetcode.html
	*
	* @author jeffwan
	* @date Apr 15, 2014
	*/
	public class LongestValidParentheses {
	public int longestValidParentheses(String s) {
	if (s == null || s.length() == 0) {
	return 0;
	}
	Stack<Integer> stack = new Stack<Integer>();
	int start = 0;
	int maxLength = 0;
	for (int i = 0; i < s.length(); i++) {
	if (s.charAt(i) == '(') {
	stack.push(i);
	} else {
	if (stack.isEmpty()) {
	start = i + 1;
	} else {
	stack.pop();
	maxLength = stack.isEmpty()? Math.max(maxLength, i - start + 1) : Math.max(maxLength, i - stack.peek());
	}
	}
	}
	return maxLength;
	}
	}

view raw LongestValidParentheses.java hosted with ❤ by GitHub