给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
1
2
3
| 输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
|
示例 2：
1
2
3
| 输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
|
示例 3：
提示：
0 <= s.length <= 3 * 104s[i] 为 '(' 或 ')'
解法：
栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
int longestValidParentheses(string s) {
stack<int> st;
st.push(-1);
int MAX = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
st.push(i);
}
else {
st.pop();
if (st.empty()) {
st.push(i);
}
else {
MAX = max(MAX, i - st.top());
}
}
}
return MAX;
}
|
记数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| int longestValidParentheses(string s) {
int left = 0;
int right = 0;
int leftMax = 0;
int rightMax = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
left++;
}
else {
right++;
}
if (left == right) {
leftMax = max(left * 2, leftMax);
}
else if (left < right) {
left = right = 0;
}
}
left = right = 0;
for (int i = s.size() - 1; i >= 0; i--) {
if (s[i] == '(') {
left++;
}
else {
right++;
}
if (left == right) {
rightMax = max(right * 2, rightMax);
}
else if (right < left) {
left = right = 0;
}
}
return max(leftMax, rightMax);
}
|
动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int longestValidParentheses(string s) {
int MAX = 0;
vector<int> dp(s.size(), 0);
for (int i = 1; i < s.size(); i++) {
if (s[i] == ')') {
if (s[i - 1] == '(') {
dp[i] = 2 + (i >= 2 ? dp[i - 2] : 0);
}
else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
dp[i] = 2 + dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0);
}
MAX = max(MAX, dp[i]);
}
}
return MAX;
}
|
