題目

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.

分析

一開始的思路是模擬。用模擬的做法主要的問題是復(fù)雜，而且容易忽視一些邊界情況。在經(jīng)歷了N次的WA+修改之后，我的代碼終于AC了。我為我的這種精神感動。
總結(jié)一些這種做法的思路：

• 從左往右遍歷字符串
• 記錄每個合法子串開始的位置
• 記錄尚未配對的"("的位置
• 記錄當(dāng)前合法子串的長度
• 若合法子串結(jié)束，取以下長度的最大值：
  1.出現(xiàn)")"且沒有尚未匹配的"("時，取得當(dāng)前合法子串長度；
  2.字符串到達末尾，取末尾位置與最后一個未匹配的"("之間的長度，以及未匹配的"("兩兩之間的長度，以及上一個合法子串串開始的位置和最左側(cè)的未匹配"("之間的長度。

實現(xiàn)一

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans=0, len=0, sl=s.size(), last=-1;
        stack<int> stk;
        for(int i=0; i<s.size(); i++){
            if(s[i]=='('){
                stk.push(i);
                len++;
            }
            else if(!stk.empty()){
                stk.pop();
                len++;
            }
            else{
                ans = max(ans, len);
                len = 0;
                last=i;
            }
        }
        if(!stk.empty()){
            int p = stk.top(), q=p;
            stk.pop();
            ans = max(ans, sl-p-1);
            while(!stk.empty()){
                q = stk.top();
                ans = max(ans, p-q-1);
                
                p = q;
                stk.pop();
            }
            ans = max(ans, q-last-1);
        }
        else{
            ans = max(ans, len);
        }
        return ans;
    }
};

思考一

這題雖然這樣做出來了，但是感覺這種做法給自己帶來的提升不大。一是真正面試的時候不會有這么多時間讓我想，二是到時候也沒有機會讓我一次次地擬合測試數(shù)據(jù)，三是這種做法有時候需要一拍腦袋得到，也挺看狀態(tài)和運氣的。
看到題解中還有用dp的方法，所以從這個角度思考做法。我覺得dp主要問題是尋找能夠具有無后效性的量，但是目前我還沒有找到什么有效方法，主要靠拍腦瓜，或者看答案=_=
這題中，我已開始想選擇使用dp[i]代表s.substr(0, i)中的最大合法括號長度，但很快發(fā)現(xiàn)需要很多補充條件。后來看了題解才知道dp[i]代表以s[i]為結(jié)尾的最大合法括號長度比較好，因為最長子串的位置在這題里確實是很重要的因素。

實現(xiàn)二

class Solution {
public:
    int longestValidParentheses(string s) {
        int sl=s.size(), ans=0;
        vector<int> dp(sl, 0);
        for(int i=1; i<sl; i++){
            int match = i - dp[i-1] -1; 
            if(s[i]==')' && match>=0 && s[match]=='('){
                dp[i] = dp[i-1] + 2;
                if(match>=1)
                    dp[i] += dp[match-1];
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

思考二

雖然這道題理解了，但是如果要我自己想，我還是不知道怎么把這個想出來。得繼續(xù)摸索要，看來未來很長時間內(nèi)要繼續(xù)拍腦瓜了。