leetCode 32.Longest Valid Parentheses (有效的最大括號) 解題思路和方法

leetCode 32.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.

 

思路：此題也是參看網上資料解出。我自己做出來的是循環O(n^3)的時間復雜度，提交果斷超時。我解法的思想是先判斷字符串為奇數還是偶數，偶數就本字符串開始，判斷是否為有效括號對，是返回，不是，長度減2，循環截取s，直到找到最大為止。

另一種方法參看了別人的思路，自己寫的代碼，總體思想是循環遍歷S,用兩個棧保存，一個保存“（）”,一個保存索引，兩個棧的操作相同。最後未出棧的元素就是無法匹配的元素，同時也是各個有效括號組的分界點，據此由各個索引相減求最大值即可。

同一個復雜字符串，方法一耗時1790ms，方法二耗時1ms.效率差距巨大。

方法一代碼：

 

	    public int longestValidParentheses(String s) {
	        int len = s.length();
	        if(len <= 1){
	            return 0;
	        }
	        int startLen;
	        int validLen = 0;
	        //長度為偶數
	        if((len & 1) == 0){
	            startLen = len;
	        }else{
	            startLen = len -1;
	        }
	        boolean isBreak = false;
	        while(startLen > 0){
	        	if(isBreak) break;
	            for(int i = 0; i + startLen <= len; i++){
	                String temp = s.substring(i,i+startLen);
	                int k = lenValid(temp);
	                if(k > validLen){
	                    validLen = k;
	                    isBreak = true;
	                    break;
	                }
	            }
	            startLen -= 2;
	        }
	        return validLen;
	    }
	    //str是否有效括號，有效返回len,無效返回-1
	    private int lenValid(String str){
	        Stack st = new Stack();
	        for(int i = 0; i< str.length();i++){
	            if(st.isEmpty() || st.peek() != '(' || str.charAt(i) != ')'){
	                st.push(str.charAt(i));
	            }else{
	                st.pop();
	            }
	        }
	        if(st.isEmpty()){
	            return str.length();
	        }
	        return -1;
	    }

方法二代碼：

 

 

    public int longestValidParentheses1(String s) {
        Stack st = new Stack();//保存()
        Stack si = new Stack();//保存()的索引
        si.push(-1);//將-1作為一個分界起始值
        for(int i = 0; i < s.length(); i++){
            if(st.isEmpty() || st.peek() != '(' || s.charAt(i) != ')'){
                st.push(s.charAt(i));//入棧
                si.push(i);
            }else{
                st.pop();//出棧
                si.pop();
            }
        }
        //si.push(s.length()-1);
        //每一個未出棧的元素都是各個有效組的分界點
        int end = s.length();//起始點
        int max = 0;//最大長度
        while(!si.isEmpty()){
            int start = si.pop();
            max = end - start - 1 > max ? end - start -1:max;
            end = start;
        }
        return max;
    }