原题地址：最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
暴力匹配
对字符串中的每个位置，找到以他开头的最长有效括号的长度，然后记录最大的长度即可。判断括号是否有效可以通过栈来完成。
具体的实现代码如下：
/**
* @param {string} s
* @return {number}
*/
const longestValidParentheses1 = function(s) {
let max = 0;
// 如果i右边的部分已经比当前max的长度要小，显然已不可能找到更长的有效括号
for (let i = 0; i < s.length - max; i ++) {
let count = 0; // 以i开始的最长有效括号的长度
let stack = []; // 判断括号是否有效的栈
let j = i;
while (j < s.length) {
if (s[j] === '(') { // 左括号就入栈
stack.push(s[j]);
} else if (!stack.pop()){ // 右括号就出栈，如果出栈失败，则证明括号已经无效，break
break;
}
j ++;
// 只有栈为空，才证明前面部分的括号已全部有效，记录有效括号长度
if (stack.length === 0) {
count = j - i;
}
}
// 比较max和count的大小
max = Math.max(max, count);
}
return max;
};
测试：
let start = new Date();
const test = longestValidParentheses1;
console.log(test("()")); // 2
console.log(test("(()")); // 2
console.log(test(")()())")); // 4
console.log(test("((()))())")); // 8
console.log(test("()(())")); // 6
console.log(new Date().getTime() - start.getTime()); // 14
时间复杂度： 双重遍历，时间复杂度为$O(n^2)$
空间复杂度： 需要一个栈来判断括号有效性，最长占用空间为n，空间复杂度为$O(n)$
动态规划
在暴力匹配中，我们对同一个子串的括号有效性进行了多次重复的计算，我们可以利用动态规划算法来减少这一过程。
利用一个数组dp来记录最长有效括号的长度，$dp[i]=x$表示以$i$结尾的最长有效括号的长度为$x$，然后我们计算$dp[i+1]$时就可利用$dp[i]$的结果。分情况考虑：
- $s[i]='('$，显然不可能存在有效括号以$s[i]$结尾，$dp[i]$为$0$
- $s[i]=')'$且$s[i-1]='('$，即
...()的形式，显然$dp[i]=dp[i-1]+2$，加上最后一对括号即可 - $s[i]=')'$且$s[i-1]=')'$，即
...))的形式，此时如果$s[i-1]$对应的有效括号的左边一位为(，即$s[i-dp[i-1]-1]='('$，则可以构成有效括号对，$dp[i]=2+dp[i-1]+dp[i-dp[i-1]-2]$，加上$dp[i-dp[i-1]-2]$是因为这种情况构成有效括号后可能会与(左边的有效括号对连起来。
具体的实现代码如下：
/**
* @param {string} s
* @return {number}
*/
const longestValidParentheses3 = function(s) {
let dp = new Array(s.length); // 记录有效括号对的长度
dp[0] = 0;
let max = 0;
for (let i = 1; i < s.length; i ++) {
if (s[i] === '(') { // 无有效括号对
dp[i] = 0;
} else {
if (s[i - 1] === '(') { // ...()的形式
dp[i] = 2 + (dp[i - 2] || 0)
} else if (s[i - dp[i - 1] - 1] === '(') { // (...))的形式
dp[i] = 2 + dp[i - 1] + (dp[i - dp[i - 1] - 2] || 0)
} else { // )...))的形式，无有效括号对
dp[i] = 0;
}
max = Math.max(dp[i], max)
}
}
return max;
};
测试：
let start = new Date();
const test = longestValidParentheses3;
console.log(test("()")); // 2
console.log(test("(()")); // 2
console.log(test(")()())")); // 4
console.log(test("((()))())")); // 8
console.log(test("()(())")); // 6
console.log(new Date().getTime() - start.getTime()); // 7
时间复杂度： 一次遍历，时间复杂度为$O(n)$
空间复杂度： 长度为$n$的$dp$数组，空间复杂度为$O(n)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 4,2019