给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
超时(217 / 230 个通过测试用例)
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
let len = s.length;
let start = 0;
let end = len;
let _result = 0;
while (start < len) {
while (end > start) {
if ((end - start + 1) % 2 && (end - start) > _result) {
let str = s.slice(start, end)
if (!match_str(str)) {
_result = Math.max(_result, end - start);
}
}
end--
}
start++
end = len;
}
return _result
function match_str(str) {
let i = 0;
while (i < str.length - 1) {
if (str[i] === '(' && str[i + 1] === ')') {
str = str.replace('()', '');
i = 0
} else {
i++
}
}
return str.length
}
};
( | ) | ( | ( | ) | ) | ... | X | X |
---|---|---|---|---|---|---|---|---|
dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | ... | dp[i-1] | dp[i] |
0 | 2 | 0 | 0 | 2 | dp[5] | ... | dp[i-1] | dp[i] |
求dp[5]:
匹配
匹配位置前一组匹配字符的长度与这次匹配的长度的和:
即:
如果5变成i的话则:如果
,则:
不匹配
那指针在该位置时得到的字符串是不满足条件的
取字符串指定位置字符可以使用'[]'也可以使用chartAt
边界处理:
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
let len = s.length,
_result = 0;
if (len === 0) return _result
let dp = Array(len).fill(0);
for (let i = 1; i < s.length; i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
}
else if (
i - dp[i - 1] > 0 &&
s.charAt(i - dp[i - 1] - 1) == '('
) {
dp[i] = dp[i - 1] +
((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0)
+ 2;
}
_result = Math.max(_result, dp[i]);
}
}
return _result
}
规则被打断
循环
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
let maxans = 0;
let stack = [-1];
for (let i = 0; i < s.length; i++) {
if (s.charAt(i) == '(') {
stack.push(i);
continue;
}
stack.pop();
if (!stack.length) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack[stack.length - 1]);
}
}
return maxans;
};
先从左向右找其中:
再从右向左找其中:
返回记录的最大值
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
let left = 0,
right = 0,
maxlength = 0;
for (let i = 0; i < s.length; i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * right);
} else if (right > left) {
left = right = 0;
}
}
left = right = 0;
for (let i = s.length - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return maxlength;
};