32. 最长有效括号

解题思路

注释比较长，耐心看，重点一是看懂dp[i]表示的是什么，那就是从j到i的合法子串长度，0 <= j <= i，重点二是j可由等式dp[i] = i - j + 1变形求得，重点三是对贪心法的理解，只取局部最优，按这个思路考虑，每次迭代尾字符要么是(要么是)，则：

  1. ...(一定不合法
  2. ...)要分情况讨论：
    1. ...()一定合法
    2. ...))可能合法，继续分情况讨论：
      1. ...((valid))，valid表示合法子串，可以为空字符串，一定合法；
      2. ...((invalid))，invalid要么是(，要么是)
        1. 例如...((())，一定是先由1分支处理，取得局部最优解，减小问题规模，再由2.2.1处理
        2. 再例如...(()))一定是先由2.2.1处理变为...valid)，取得局部最优解，减小问题规模，继续由2处理；

可见2.2.2的invalid无论是什么，都可以通过该策略取得局部最优，减小问题规模后重新应用该策略，这是贪心法的特征；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
    let max = 0;
    const dp = [0]; // dp[x]表示从y到x的合法子串长度，0 <= y <= x，此处有一个相等关系，dp[x] = x - y + 1；

    for (let i = 1; i < s.length; i++) {
        if (s[i] === "(") { // 以 ( 结尾必不合法
            dp[i] = 0;
        } else if (s[i - 1] === "(") { // 以 ) 结尾，且前一个字符为 (，合法
            // 结果为dp[i - 2] + 2，i - 2可能越下界，越界用0缺省
            dp[i] = (dp[i - 2] || 0) + 2;
        } else if (s[i - 1] === ")" && s[i - 1 - dp[i - 1]] === "(") { // 以 ) 结尾，且前一个字符为 )，且再往前有子串((，合法
            // 注意此处，x = i - 1，dp[x]已知
            // 求y到x的合法字串的首字符下标，就也是求y
            // 上式变形再代入可得y = x + 1 - dp[x] = i - dp[i - 1]；
            // 于是得到s[y]，如果s[y]和s[y-1]都是(，s[x]和s[x+1]都是 )，形如((...))，则合法
            // 其中省略号必然合法，因为该分支只会判断最近的一对合法的((...))，即只取局部最优解，对于该分支不合法的情况例如((())，(()))，由其他分支先处理或后处理；
            // 最后结果还要加上((...))之前的邻接合法子串长度，即dp[y-2]=dp[i-dp[i-1]-2]；
            dp[i] = (dp[i - 2 - dp[i - 1]] || 0) + dp[i - 1] + 2;
        } else {
            dp[i] = 0;
        }
        max = Math.max(dp[i], max);
    }

    return max;
};