【leetcode with java】32 Longest Valid Parentheses O(n)

这个题目leetcode上提示用动态规划，但是那样要O(n^2)。我自己想出了一个O(n)的算法，并提交通过。

【题目】

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.Tags： Dynamic Programming ,String

【思路】

注意到一个规律：只要从开头当前位置的子串中左括号的个数小于右括号的个数，那么该子串便不能够再同右边任何子串构成合法子串。

这时，只要记录当前子串的最长合法子串，然后从下一个位置开始查找最长子串。

局部最长合法子串长度的记录：这里用到了一个Hashtable<Integer，Integer>，key为记录该长度时栈中左括号的个数，，value为每次遇

到右括号时该右括号所在合法子串的长度。

【上码】

import java.util.Hashtable;import java.util.Stack;/* * 参考：为参考他人算法 * T = O(n) * leetcode上提示用动态规划，但是那样要O(n^2) */public class Solution {public int longestValidParentheses(String s) {int maxLen = 0;if(s==null||s.length()==0)return maxLen;Stack<Character> stack = new Stack<Character>();Hashtable<Integer, Integer> hashtable = new Hashtable<Integer, Integer>();int len = s.length();int left=0,right=0,L=0;for(int p=0;p<len;p++){if(s.charAt(p) == ')')if(stack.isEmpty()){//maxLen = maxLen>L?maxLen:L;right++;}else if(stack.peek()=='('){stack.pop();Integer v1 = hashtable.get(left);if(v1 != null){L += v1;hashtable.remove(left);}left–;L+=2;Integer v2 = hashtable.get(left);if(v2 != null){L += v2;}hashtable.put(left, L);}else {stack.push(')');right++;}else {stack.push('(');left++;}maxLen = maxLen>L?maxLen:L;L = 0;if(left<right){stack.clear();hashtable.clear();left = 0;right = 0;//L = 0;}}return maxLen;}}

接受失败也等于给了自己从零开始的机会，接受失败更是一种智者的宣言和呐喊;