题解 | #最长的括号子串#

方法一：栈

• 括号匹配问题可以用栈的先进后出特性解决，传统括号匹配中栈中存放的是左括号，而现在要求的是最长的括号子串，那么栈中应该存放左括号的下标，用当前右括号下标减去左括号下标可得到匹配的括号子串的长度。
• 当前右括号下标应该减去的是弹出当前栈顶左括号下标后剩下的栈顶左括号下标，因为弹出当前左括号下标表示当前左括号和当前右括号匹配，而中间可能有些括号被匹配消掉了，剩下的栈顶左括号下标表示的就是最开始没被消掉的左括号下标，因此当前右括号下标减去它就得到当前匹配的括号子串长度。
• 当栈中的所有左括号都被匹配消掉时，栈中只剩下一个栈底元素存放最后一个没有被匹配的右括号下标，他表示从这个下标之后就是匹配的括号串，因此当前右括号下标应该减去它得到匹配的括号子串长度。初始时，栈中没有左括号，栈底存放的最后一个没有被匹配的右括号下标设为-1。由于栈中一直有一个元素，所以判断栈不为空为栈的长度大于1。

/**
  * 
  * @param s string字符串 
  * @return int整型
  */
function longestValidParentheses( s ) {
    // write code here
    const bracketStack = [];
    let maxBracketLength = 0;

    bracketStack.push(-1); // 栈底存放最后一个没有被匹配的右括号的下标，初始为-1
    for (let i = 0; i < s.length; ++i) {
        if (s[i] === "(") {
            bracketStack.push(i);  // 遇到左括号存放左括号的下标
        }
        else if (s[i] === ")") {
            if (bracketStack.length > 1) {
                bracketStack.pop();  // 先弹出一个左括号，表示跟当前的右括号匹配
                // 当前右括号下标减去弹出当前左括号下标后的元素表示当前匹配的子串长度（因为中间可能有些括号已经被匹配消掉了）
                // 极端情况下，即栈中的左括号已经全被消掉，此时当前右括号下标减去的是栈中唯一剩下的栈底元素（最后一个没被匹配的右括号下标），得到当前匹配到的子串长度
                maxBracketLength = Math.max(maxBracketLength, i-bracketStack[bracketStack.length-1]);  
            }
            else {
                bracketStack[0] = i;  // 只在栈中无左括号下标时（此时栈中只剩下一个元素，即最后一个没有被匹配的右括号的下标），更新栈底元素
            }
        }
    }

    return maxBracketLength;
}
module.exports = {
    longestValidParentheses : longestValidParentheses
};

方法二：动态规划

DP数组应该保存什么？

题目要求的是某个字符串最长的匹配括号子串长度，DP数组应该用一维DP数组（思考用二维DP的区别），dp[i]保存的是字符串的第i个字符结尾的括号子串的最大匹配括号子串的长度（这个括号子串不一定是从字符串的开头开始），由于是连续性质，所以最后一个字符为右括号时才有可能成为匹配的括号子串。

最小子问题

• 当字符串中只有一个字符时，匹配括号长度为0
• 当字符串的结尾字符为左括号时，匹配括号长度为0，因为以左括号结尾的括号子串肯定是不匹配的括号子串。

如何思考状态转移方程？

• 当前字符为右括号时，如果前一个字符是左括号，说明当前右括号和这个左括号形成匹配括号串，在这个左括号前面的字符结尾的匹配括号子串长度加上这对匹配括号长度就是当前位置结尾的匹配括号子串长度。dp[i] = dp[i-2]+2
• 当前字符为右括号时，如果前一个字符是右括号，说明与当前右括号匹配的左括号可能在更前面（即在i-dp[i-1]-1位置），这两个括号包裹i-1结尾的匹配括号串，如果与当前右括号匹配的左括号前面还有连续的匹配括号串，那么最终的括号串长度还要加上这个连续的匹配括号串长度。dp[i] = dp[i-1]+2+dp[i-dp[i-1]-2]

参考

https://blog.nowcoder.net/n/9e4b3953abb84149b04c95bf89d7772e?f=comment

/**
  * 
  * @param s string字符串 
  * @return int整型
  */
function longestValidParentheses( s ) {
    // write code here
    const dp = new Array(s.length).fill(0);  // dp保存s从开头到第i个字符结束的子串中最大的匹配括号的子串长度
    let maxBracketLength = 0;

    for (let i = 1; i < s.length; ++i) {
        if (s[i] === ")") {
            if (s[i-1] === "(") {  // 如果前一个字符是左括号，说明当前右括号和这个左括号形成匹配括号串，在这个左括号前面的子串的匹配括号长度加上这对匹配长度就是当前位置的子串中最大匹配括号的子串长度
                dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
            }
            else if (i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] === "(") {  // 如果前一个字符是右括号，说明与当前右括号匹配的左括号可能在更前面，这两个括号包裹i-1结尾的匹配括号串，如果与当前右括号匹配的左括号前面还有连续的匹配括号串，那么最终的括号串长度还要加上这个连续的匹配括号串长度
                dp[i] = dp[i-1] + 2 + (i-dp[i-1]-2 >= 0 ? dp[i-dp[i-1]-2] : 0);
            }
            maxBracketLength = Math.max(maxBracketLength, dp[i]);
        }
    }
    
    return maxBracketLength;
}
module.exports = {
    longestValidParentheses : longestValidParentheses
};