32-最长有效括号

LeetCode 32. Longest Valid Parentheses

LeetCode-32

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

Example 1:

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

Example 2:

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

method 1: 动态规划

dp[i]：表示以i结尾的最长有效括号长度

• s[i]=='('：则无法与之前的匹配，所以dp[i]=0
• s[i]==')'：有可以分为两种情况
  • 如果s[i-1]=='('，则s[i-1],s[i]就可以组成一对匹配的括号，所以括号的长度应该在dp[i-2]的基础上增加2，也就是dp[i]=dp[i-2]+2
  • 如果s[i-1]==')'，还要看下是否存在嵌套的情况，((...))，因为dp[i-1]表示的就是以i-1结尾的最长匹配括号长度，所以我们可以找到与s[i]匹配的位置，也就是i-dp[i-1]-1，如果这个位置上是(，那就可以匹配了，所以dp[i]=dp[i-1]+2，同时这个匹配的位置前面可能还有很多的匹配的括号，()...()((...))，并且其最大长度就保存在dp[i-dp[i-1]-2]，所以也应该加上，所以应该是dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2

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

method 2: 栈

• 遇到(就把下标入栈
• 遇到)就把栈顶元素出栈
  • 如果此时栈非空，当前下标和此时的栈顶相减就是匹配的长度，更新结果
  • 如果栈是空的，说明没有与之匹配的(，所以把当前下标入栈，作为分隔点

int longestValidParentheses(string s) {
    stack<int> st;
    st.push(-1);    // 虚拟的'('，从-1后面开始有效
    int res = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {  // (入栈
            st.push(i);
        }
        else {
            st.pop();   // )出栈
            if (st.empty()) {   // 栈空把当前元素入栈
                st.push(i);
            }
            else {  // 栈非空就计算长度，更新结果
                res = max(res, i - st.top());
            }
        }
    }
    return res;
}