Difficulty:: Hard
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
1
2
3
| Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
|
Example 2:
1
2
3
| Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
|
Solution
Language: Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
int max = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
max = Math.max(max, i - stack.peek());
}
}
}
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
| class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
if (stack.peek() == -1) {
stack.push(i);
} else if (s.charAt(i) == '(') {
stack.push(i);
} else if (s.charAt(stack.peek()) == '(') {
stack.pop();
maxLen = Math.max(maxLen, i - stack.peek());
} else {
stack.push(i);
}
}
return maxLen;
}
}
|