[leetcode]Longest Valid Parentheses

NO IMAGE

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.


在valid parentheses問題中,我們可以用stack來檢驗括號對,也可以通過count來檢驗。遇到”(“就加一,遇到”)”就減一。找到一對括號就在最終結果上加2。
我們用value[i]來表示當前位置的最長括號。
括號之間的關係有兩種,包含:() or (()) or ((()))和相離()() or ()(())。

public class Solution {
    public int longestValidParentheses(String s) {
        char[] chs = s.toCharArray();
        int[] value = new int[chs.length];
        int open = 0;
        int max = 0;
        
        for(int i=0; i < chs.length; i  ){
            if(chs[i] == '(') open  ;
            if(chs[i] == ')' && open > 0) {
                //包含關係,通過最近的括號長度來改變。
                // ()    dp[1] = dp[0]  2
                // (())  dp[2] = dp[1]  2 =2,  dp[3] = dp[2]  2 = 4
                value[i] = 2   value[i-1];
                //相離關係,通過相離的括號長度來改變。
                // ()()  dp[3] = dp[3]   dp[1] = 2   2 = 4
                if(i-value[i] > 0){
                    value[i]  = value[i-value[i]];
                }
                open--;
            }
            if(value[i] > max) max = value[i];
        }
        
        return max;
    }
}