题目描述

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 "()()"

题意：给一个包含(和)的字符串，找到最长的合法的括号序列。

算法1

(暴力枚举) $O(n^2)$

题解1:Brute force.遍历所有的’(‘，往后开始扫描字符串，找到最长的合法括号序列。时间复杂度$O(n^2)$。

    int longestValidParentheses(string s) {
        int res = 0,n = s.length();
        for(int i = 0 ; i < n ; i ++)
        {    
            if(s[i] =='(')
            {       //  bal等于0时说明找到了一个合法序列，小于0时说明不合法了
                int cur = 0,bal = 1;
                for(int j = i + 1;j < n ; j ++)
                {
                    if(s[j] == '(') bal ++;
                    else if(s[j] == ')') bal --;
                    if(bal == 0) cur = j - i + 1;
                    if(bal < 0) break;
                }
                res = max(res,cur);
            }
        }
        return res;
    }

后面三种方法都是$O(n)$的

算法2

使用栈来模拟操作。栈顶保存当前扫描的时候，当前合法序列前的一个位置位置下标是多少。初始时栈中元素为-1。然后遍历整个字符串

• 如果s[i] =='('，那么把i进栈。
• 如果s[i] == ')',那么弹出栈顶元素 （代表栈顶的左括号匹配到了右括号）
• 如果此时栈为空，将i进栈。说明之前没有与之匹配的左括号，那么就将当前的位置入栈。
• 否则，i - st.top()就是当前右括号对应的合法括号序列长度。

    int longestValidParentheses(string s) {
        int res = 0,n = s.length();
        stack<int> st;
        st.push(-1);
        for(int i = 0 ; i < n ; 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;
    }

算法3

题解3:动态规划。

状态表示：dp[i]表示以下标i结尾的最长合法括号序列长度，所有以左括号结尾的序列都不是合法括号序列，所以我们从前往后扫描，如果遇到了右括号s[i],那么有两种情况

• s[i - 1] = '('，那么很明显dp[i] = dp[i - 2] + 2
• s[i - 1] = ')'，我们需要判断i - dp[i - 1] - 1的位置是否是左括号，这个位置是以s[i - 1]结尾的最长合法括号序列开头的前一个字符。如果他不是左括号，说明当前右括号没有合法匹配。
• 如果是左括号，那么dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]。分别代表以s[i - 1]结尾的最长合法括号长度，s[i]的右括号和对应的左括号，s[i]对应的左括号前面一个位置结尾的最长合法括号序列

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

算法4

题解4:双向扫描。不需要使用额外空间

第一遍从左往右扫描，left和right分别代表当前合法的左括号个数和右括号个数。遇到左括号left ++，遇到右括号right ++，如果left = right，说明找到了一个合法的括号对，更新答案，如果left < right，说明后面怎么匹配都不可能合法了，此时把left和right置为0。

但是这样对于((())的括号序列，得不到正确解，因此我们继续从右往左匹配一次。

第二遍第一遍从右往左扫描，left和right分别代表当前合法的左括号个数和右括号个数。遇到左括号left ++，遇到右括号right ++，如果left = right，说明找到了一个合法的括号对，更新答案，如果left > right，说明前面怎么匹配都不可能合法了，此时把left和right置为0。

    int longestValidParentheses(string s) {
        int res = 0,n = s.length(), left = 0,right = 0;
        for(int i = 0 ; i < n ; i ++)
        {
            if(s[i] == '(') left ++;
            else right ++;
            if(left == right) res = max(res,2 * right);
            if(left < right) {left = 0;right = 0;}
        }
        left = 0,right = 0;
        for(int i = n - 1;i >= 0; i --)
        {
            if(s[i] == ')') right ++;
            else left ++;
            if(left == right) res = max(res,2 * right);
            if(right < left) {left = 0;right = 0;}
        }
        return res; 
    }