Leetcode Longest Valid Parentheses 結題報告

Leetcode 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.
https://oj.leetcode.com/problems/longest-valid-parentheses/
分析，求出一串由：‘(’和‘)’組成的字符串中合法()配對的長度。例如：(()()，結果是4。((()))結果是6。())()()結果是4。
解題思路：最容易想到的解法就是窮舉法，計算任意兩點(i到j)之間有多少個合法的()串，借助動態規劃可以得到結果。算法復雜度為：
想要O(n)的解法需要一點技巧，也要弄清楚幾種情況：

AC代碼如下所示：

public class Solution {
    public int longestValidParentheses(String s) {
        if(s==null||s.length()==0) {
            return 0;
        }
        int start     = -1;
        int maxLength = 0;
        Stack stack   = new Stack();
        for(int i=0;i