NC49 最长的括号子串

解法

function longestValidParentheses( s ) {
    // write code here
    let dp = new Array(s.length).fill(0)
    let res = 0
    
    for(let i = 1; i < s.length; ++i){
        if(s[i] === ')'){
            if(s[i - 1] === '('){
                dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2
            }else{
                if(s[i - dp[i - 1] - 1] === '('){
                    dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0)
                }
            }
            res = Math.max(res, dp[i])
        }
    }
    return res
}

解析

经典的dp算法，dp数组中的dp[i]代表以s[i]为结尾的最长有效括号长度。有效括号一定以‘)’结尾，只需要关注s[i] === ‘)’的情况即可。

最后一个字符有效时又可分为两种情况

1. 形如…(),即s[i - 1] === ‘(‘，此时只需要判断dp[i - 2]的情况即可
2. 形如（（…））,此时必须保证s[i - dp[i - 1] - 1] === ‘(‘(最左边的括号与s[i]匹配)，计算完这一部分后要注意最左边的部分（s[i - dp[i - 1] - 1左侧的部分），因为由于新括号的加入，导致原来不能构成有效括号的部分一起构成了新的有效括号，比如()((…))