問題

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.

分析

方法一：棧

遍歷字符串，如果當(dāng)前字符為 ( , 入棧徙邻；如果是 ) 爹凹，檢測棧的情況：如果棧為空，入棧饿自；否則檢查棧頂，如果為 ( ，出棧哑姚；否則入棧。注意芜茵，也要把當(dāng)前字符的下標(biāo)入棧叙量。
將棧的元素一一出棧，即可得到每一段合法的括號表達(dá)式的長度九串。假設(shè)字符串為")()(()))()("绞佩，遍歷完之后，棧應(yīng)該變成 ) 0, ) 7, ( 10蒸辆≌髁叮可以清楚地看到，原字符串有兩段合法的括號表達(dá)式躬贡，長度分別為7 - 0 - 1 = 6谆奥、10 - 7 - 1 = 2。最長長度為6拂玻。

方法二：動態(tài)規(guī)劃

假設(shè)待驗證字符串為S

1. 狀態(tài)表
   dp[i] 表示以S[i - 1]作為結(jié)尾的最長合法字符串的長度
2. 初始狀態(tài)
   dp[0] = dp[1] = 0 長度為0或者1的字符串顯然不合法
3. 狀態(tài)轉(zhuǎn)移方程
   dp[i] = dp[i - 2] + 2 if s[i - 1] == ')' && s[i - 2] = '('
   注：表示這種情況：...() **
   顯然dp[i]的大小等于...的最大合法字符串的長度（dp[i - 2]）+2
   dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]; if s[i - 1] == ')' && s[i - 2] = ')' && s[i - 2 - dp[i - 1]] == '('
   注：表示這種情況：...(()) **
   第一個 ( 是s[i - 2 - dp[i - 1]] 酸些，第一個 ) 是s[i - 2]，第二個 ) 是s[i - 1]檐蚜∑嵌總長度=...的最大合法字符串的長度（dp[i - 2 - dp[i - 1]]）+ 2（s[i - 2 - dp[i - 1]]和s[i - 1]匹配的一對括號）+ dp[i - 1]（中間的兩個括號）

要點

• 熟練運用棧和動態(tài)規(guī)劃；
• 動態(tài)規(guī)劃分為兩種闯第，一種狀態(tài)本身就是所求的變量市栗，另一種則不是，但是所求的變量可以在更新狀態(tài)表的過程中得到。

時間復(fù)雜度

O(n)

空間復(fù)雜度

O(n)

代碼

方法一

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<pair<char, int>> es;
        for (int i = 0; i < s.size(); i++) {
            if (es.empty() || s[i] == '(') es.push(make_pair(s[i], i));
            else {
                if (es.top().first == '(') es.pop();
                else es.push(make_pair(s[i], i));
            }
        }

        int longestLen = 0, last = s.size();
        while (!es.empty()) {
            longestLen = max(longestLen, last - es.top().second - 1);
            last = es.top().second;
            es.pop();
        }
        longestLen = max(longestLen, last);
        return longestLen;
    }
};

方法二

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