32. Longest Valid Parentheses

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

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

如果當前這個index i的char是（，可以先跳過，如果是）再檢查i - 1的char，如果是（，則s[i - 1]和s[i]可以形成一個長度為2的valid parentheses，如果i - 2還是有效的index，則longest[i] = longest[i - 2] + 2，不然longest[i] = 2。 如果s[i - 1]是），代表連續兩個）在一起出現，longest[i - 1]代表以s[i - 1]結尾的）形成的最長valid parentheses長度，這時先確認i - 1 - longest[i - 1]是否為有效的index，如果是而且s[i - 1 - longest[i - 1] ]是（，那麼這個尾巴連續兩個）出現的括號在頭的地方就有對應到的兩個（。最後再確認i - 2 - longest[i - 1]是否為有效的index，如果是的話再把longest[i - 2 - longest[i - 1] ]加上。

// Dynamic programming
int longestValidParentheses(string s) { // time: O(n); space: O(n)
    int n = s.length(), res = 0;
    if (n <= 1) return res;
    vector<int> longest(n, 0);
    for (int i = 1; i < n; ++i) {
        if (s[i] == '(') continue;
        if (s[i] == ')') {
            if (s[i - 1] == ')') {
                if (i - 1 - longest[i - 1] >= 0 && s[i - 1 - longest[i - 1]] == '(') {
                    longest[i] = longest[i - 1] + 2 + ((i - longest[i - 1] - 2) >= 0? longest[i - longest[i - 1] - 2] : 0);
                }
            } else { // s[i - 1] == '('
                longest[i] = (i >= 2 ? longest[i - 2] : 0) + 2;
            }
        }
        res = max(res, longest[i]);
    }
    return res;
}

// Stack
int longestValidParentheses(string s) { // time: O(n); space: O(n)
    int n = s.length(), res = 0;
    if (n <= 1) return res;
    int start = 0; // the starting position of valid parentheses
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '(') st.push(i);
        else {
            if (st.empty()) start = i + 1;
            else {
                st.pop();
                res = max(res, (st.empty() ? i - start + 1: i - st.top()));
            }
        }
    }
    return res;
}