動機

以後遇到回文優先考慮中心展開

Problem

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

 

Example 1:

Input: s = (()Output: 2Explanation: The longest valid parentheses substring is ().

Example 2:

Input: s = )()())Output: 4Explanation: The longest valid parentheses substring is ()().

Example 3:

Input: s = Output: 0

 

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is '(', or ')'.

Ver1: TLE

int dp[2000][2000] = {0};
class Solution {
public:
    int getEval(int i,int j) { return !dp[i][j] ? -1 : dp[i][j]; }
    bool notEval(int i,int j) { return dp[i][j] == 0;}
    int f(string &s,int i,int j) {
        if(i > s.size() || j < 0)
            return -1;
        else if(i >= j)
            dp[i][j] = -1;
        if(notEval(i,j)) {
            if(s[i] == '(' && s[j] == ')') { // !!
                for(int k=i+1;k+1<j;k++)
                    if(s[k] == ')' && s[k+1] == '(') // !!
                        if(f(s,i,k) > 0 && f(s,k+1,j) > 0)
                            dp[i][j] = max(getEval(i,j),f(s,i,k)+f(s,k+1,j));
                dp[i][j] = max(getEval(i,j), f(s,i+1,j-1) > 0 ? f(s,i+1,j-1)+2 : -1);
            }
            else
                dp[i][j] = -1;
        }
        return getEval(i,j);
    }
    void initDP(string &s) {
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<s.size();i++)
            dp[i][i] = -1;
    }
    void find_out_single_pair(string &s) { // 找()
        for(int i=0;i+1<s.size();i++)
            if(s[i] == '(' && s[i+1]==')')
                dp[i][i+1] = 2;
    }
    int longestValidParentheses(string s) {
        initDP(s);
        find_out_single_pair(s);
        int ans = 0;
        for(int i=0;i<s.size();i++)
            for(int j=0;j<s.size();j++)
                ans = max(ans,f(s,i,j));
        //ans = f(s,0,s.size()-1);
        //for(int i=0;i<s.size();i++) {
        //    for(int j=0;j<s.size();j++)
        //        cout << dp[i][j] << ' ';
        //    cout << '\n';
        //}
        return ans;
    }
};

Ver2: TLE

等等，為什麼每次run test拋出來的時間都不一樣啊 一下76ms，一下超時

int dp[2000][2000] = {0};
class Solution {
public:
    int ans = 0;
    void initDP(string &s) {
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<s.size();i++)
            dp[i][i] = -1;
        ans = 0;
    }
    void setDP(int i,int j,int val) {
        dp[i][j] = val, ans = max(ans,val);
    }
    
    bool isPair(string &s,int i,int j) { return s[i] == '(' && s[j] == ')'; }
    void compDiv(string &s,int i,int j) {
        for(int x=i+1;x+1<j;x++) // [i~k] + [k+1~j]
            if(isPair(s,x+1,x) && dp[i][x] > 0 && dp[x+1][j] > 0)
                setDP(i,j,dp[i][x] + dp[x+1][j]);
    }
    int longestValidParentheses(string s) {
        initDP(s);
        for(int i=0;i+1<s.size();i++)
            if(isPair(s,i,i+1)) {
                setDP(i,i+1,2);
                for(int k=1;i-k >= 0 && (i+1)+k < s.size() && isPair(s,i-k,(i+1)+k);k++)
                    setDP(i-k,(i+1)+k,dp[i-(k-1)][(i+1)+(k-1)] + 2);
            }
        for(int k=1;k<s.size();k++)
            for(int j=k,i=0;j<s.size();j++,i++)
                if(isPair(s,i,j)) {
                    compDiv(s,i,j);
                    if(i+1 < s.size() && j-1 >= 0 &&　dp[i+1][j-1] > 0)
                        setDP(i,j,max(dp[i][j], dp[i+1][j-1] + 2));
                }       
        /*
        for(int i=0;i<s.size();i++) {
            for(int j=0;j<s.size();j++)
                cout << dp[i][j] << ' ';
            cout << '\n';
        }
        */
        return ans;
    }
};

Ver3: AC

定義: dp[i]是到i為止最長的括號長度

int dp[100000] = {0};
int ans = 0,len=0;
class Solution {
public:
    void initDP(string &s) {
        memset(dp, 0, sizeof(dp));
        ans = 0;
        len=s.size();
    }
    bool isLegal(int i) { return i >= 0 && i < len; }
    bool isPair(string &s,int i,int j) { return isLegal(i) && isLegal(j) && s[i] == '(' && s[j] == ')'; }
    bool isCons(string &s,int i,int j) { return isLegal(i) && isLegal(j) && s[i] == ')' && s[j] == ')'; }
    int getDP(int i) {
        return isLegal(i) ? dp[i] : 0;
    }
    void setDP(int i,int val) {
        dp[i] = val, ans = max(ans,val);
    }
    int longestValidParentheses(string s) {
        initDP(s);
        for(int i=1;i<s.size();i++)
            if(isPair(s,i-1,i))
                setDP(i,getDP(i-2)+2);
            else if(isCons(s,i-1,i) && getDP(i-1) > 0 && isPair(s,i-getDP(i-1)-1,i))
                setDP(i,getDP(i-1)+2+getDP(i-2-getDP(i-1)));
        return ans;
    }
};

case study

從左邊往右看，左是開頭，只有對應的右就會被算進長度，但一旦右超過，左就再也不能被算，就要重新計數

所以可以左右兩邊都算，找最大的

public class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right >= left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left >= right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
}