LeetCode 32. Longest Valid Parentheses

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.

题目大意就是给你字串全是'('和')'构成的字符串，求最长合法字串和长度。（合法的意思指在该子串中，每一个左子串都有一个右边的右子串与之对应）

这道题最简单的思路就是 $O(n^2)$ 的方法， 从左到右枚举起点位置就可以了。

于是代码可以这样写

class Solution {
public:
    int longestValidParentheses(string s) {
        int mx = 0;
        for(size_t i = 0; i < s.size(); ++ i)
        {
            if(s[i] == '(')
            {
                int res = 0;
                for(size_t j = i; j < s.size(); ++ j)
                {
                    if(s[j] == '(')
                        res ++;
                    
                    if(s[j] == ')')
                    {
                        if(res > 0)
                            res --;
                        else
                            break;
                    }
                    if(res == 0)
                        mx = max(mx, int(j-i+1));
                }
            }
        }
        return mx;
    }
};

由这个方法来拓展。

• $1.$假设在一串合法子串str中，从str的起点位置开始，左括号的数目一定要小于等于右括号的数目。用f(a)来表示a字符的数目， 那么即f('(') >= f(')')。
• $2.$那么对于str后面的下一个字符一定是')', 之所以这个字符之所以没有在str里面，是因为加上该字符f('(') < f(')')。
• $3.$断开str，设断开str后前面子串为m，后面子串为n， 在m中f('(') >= f(')')这是一定的（str是合法子串的条件），又因为在str中f('(') == f(')')， 所以在n中f('(') <= f(')')， 所以子串n与下一个字符')', 一定不能组成一个合法子串。
• $4.$所以就有O(n)的方法来找出最长子串了，判断该子串是合法子串后， 不需要再回到该子串的起点位置，来枚举下一个起点(由$3$可知)， 直接从该子串的终点开始枚举即可。
• 对于假设条件f('(') >= f(')')， 因为在合法子串中只有两种情况f('(') >= f(')')和f('(') <= f(')')， 所以将字符串颠倒一下顺序求两边即可。

class Solution {
    
    int longest(string &s)
    {
        int mx = 0;
        for(size_t i = 0; i < s.size(); ++ i)
        {
            if(s[i] == '(')
            {
                int res = 0, t = i;
                for(; i < s.size(); ++ i)
                {
                    if(s[i] == '(')
                        res ++;
                    
                    if(s[i] == ')')
                    {
                        if(res > 0)
                            res --;
                        else
                            break;
                    }
                    if(res == 0)
                        mx = max(mx, int(i-t+1));
                }
            }
        }
        return mx;
    }
public:
    int longestValidParentheses(string s) {
        int a = longest(s);
        reverse(s.begin(), s.end());
        for(size_t i = 0; i < s.size(); ++ i)
            if(s[i] == '(')
                s[i] = ')';
            else
                s[i] = '(';
        int b = longest(s);
        return max(a, b);
    }
};