[leetcode]Longest Valid Parentheses

新博文地址：[leetcode]Longest Valid Parentheses

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.

 这道题不会做，看了别人的算法，感觉好腻害。算法具体思想是，先把所有匹配的括号对，变成一样的标记，比如‘0’，例如：）（）（）（）（（）可以变成）000000（00，这样再求是不是容易多了？

掉渣天啊！！！

不罗嗦了，代码如下：

 

    public int longestValidParentheses(String s) {
		if(s == null || s.length() < 2){
			return 0;
		}
		char[] sToArray = s.toCharArray();
		int max= 0;
		for(int i = 1; i < s.length(); i++){
			if(sToArray[i] ==')'){
				for(int j = i - 1; j >= 0; j--){
					if(sToArray[j] =='('){
						sToArray[i] = sToArray[j] = '0';
						break;
					}
				}
			}
		}
		int length = 0;
		for(int i = 0 ; i < sToArray.length; i++){
			if(sToArray[i] == '0'){
				length++;
				max = length > max ? length : max;
			}else {
				length = 0;
			}
		}
		return max;	
	}

 

 

评论

2 楼 huntfor 2014-08-06  

249326109 写道

这个算法的复杂度有考虑过么

O(n^2)....

1 楼 249326109 2014-08-06  

这个算法的复杂度有考虑过么