leetcode 32. 最长有效括号
题目详情
题目链接 给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()”示例 2: 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”
我的代码
class Solution {
public:
int longestValidParentheses(string s
) {
int len
= s
.size();
if (len
< 2) {
return 0;
}
int res
= 0;
vector
<int> flags(len
, 0);
for (int i
= 0; i
< len
; ++i
) {
if (s
[i
] == ')') {
continue;
}
int left
= 1;
for (int loc
= i
+ 1; (left
!= 0) && (loc
< len
); ++loc
) {
if (s
[loc
] == '(') {
++left
;
} else {
--left
;
if (left
== 0) {
flags
[loc
] = loc
- i
+ 1 + (i
- 1 >= 0 ? flags
[i
- 1] : 0);
res
= max(res
, flags
[loc
]);
break;
}
}
}
}
return res
;
}
};
我的成绩
执行结果：通过 执行用时：1332 ms, 在所有 C++ 提交中击败了5.21%的用户 内存消耗：7.6 MB, 在所有 C++ 提交中击败了100.00%的用户
一些想法
本道题我是先求以每个左括号为起点的有效括号个数，然后存储flag数组内。
执行用时为 4 ms 的范例
class Solution {
public:
int longestValidParentheses(string s
) {
int size
= s
.length();
vector
<int> dp(size
, 0);
int maxVal
= 0;
for(int i
= 1; i
< size
; i
++) {
if (s
[i
] == ')') {
if (s
[i
- 1] == '(') {
dp
[i
] = 2;
if (i
- 2 >= 0) {
dp
[i
] = dp
[i
] + dp
[i
- 2];
}
} else if (dp
[i
- 1] > 0) {
if ((i
- dp
[i
- 1] - 1) >= 0 && s
[i
- dp
[i
- 1] - 1] == '(') {
dp
[i
] = dp
[i
- 1] + 2;
if ((i
- dp
[i
- 1] - 2) >= 0) {
dp
[i
] = dp
[i
] + dp
[i
- dp
[i
- 1] - 2];
}
}
}
}
maxVal
= max(maxVal
, dp
[i
]);
}
return maxVal
;
}
};
思考
参考官方解答。
