LC

题目

思路

栈

合法括号匹配问题一般都要用到两个性质：

  • 合法串的左括号 = 右括号
  • 合法串的任意前缀，都存在左括号 ≥ 右括号

利用性质2，可以证明：如果存在一个（且下标最小为$i$）的右括号，使得$s[0-i]$中，右括号的数量大于左括号，那么最大合法串一定不会横跨$i$。

这些满足上面条件右括号把整个串分割成了若干段。

直观上看，可以想象括号配对是一个找对象的过程。左括号是妹子，右括号是准备找妹子的男同志们。举个下面的简单例子：

( ( ) ) ) ( )

第一个和第二个妹子都很幸运地被三号和四号男嘉宾牵走，而可怜的五号男嘉宾一进来发现已经没有妹子了(T_T) 而六号妹子和七号男嘉宾却在一起了。

现在让我们把找到对象的（就是合法配对的）妹子和男嘉宾手牵手连成一起，这个可怜的男嘉宾就像一堵墙，会挡在两组配对的人中间。因为妹子们喜新厌旧（左括号只会向后匹配），只会跟新来的男嘉宾走，对于已经等候多时的五号男嘉宾毫无兴趣。

利用上面的这个性质，只需要遍历一下每一段里面的合法串，再取max即可。

DP

定义f[i]表示以$i$结尾的串中，最大合法串的长度。

推出状态计算的表达式：

只讨论s[i] == ')'的情况

① 当s[i - 1] == '('时 f[i] = f[i - 2] + 2
② 当s[i - 1] == ')'时 f[i] = f[i - 1] + 2 + f[i - f[i - 1] - 2]。表示经过中间一长段合法串的最左边是否有一个左括号待匹配，如果有，那么这项会取到，如果没有，那么这项为0。比如：( ()()()() )，经过中间一堆合法串，最左边有一个待匹配的左括号，所以这项可以更新。

代码

栈做法

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;

        int res = 0;
        for(int i = 0, start = -1; i < s.size(); i++) {
            if(s[i] == '(') stk.push(i);
            else{
                if(stk.size()) {
                    stk.pop();
                    if(stk.size()) {
                        res = max(res, i - stk.top());
                    } else {
                        res = max(res, i - start);
                    }
                } else {
                	// 此时说明本段已经枚举完了，跳到下一段
                    start = i;
                }
            }
        }
        return res;
    }
};

DP做法

class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty()) return 0;
        int n = s.size();
        vector<int> f(n);

        for(int i = 1; i < n; i++) {
            if(s[i] == ')') {
                if(s[i - 1] == '(') {
                    if(i >= 2) f[i] = f[i - 2] + 2;
                    else f[i] = 2;
                } else {
                    int st = i - f[i - 1] - 1;
                    if (st == 0 && s[st] == '(') f[i] = f[i - 1] + 2;
                    else if(st > 0 && s[st] == '(') f[i] = f[i - 1] + 2 + f[st - 1];
                }
            }
        }
        int res = 0;
        for(auto c: f) res = max(res, c);
        return res;
    }
};