forked from leetcoders/LeetCode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLongestValidParentheses.java
More file actions
75 lines (70 loc) · 2.31 KB
/
LongestValidParentheses.java
File metadata and controls
75 lines (70 loc) · 2.31 KB
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
Author: Andy, nkuwjg@gmail.com
Date: Dec 20, 2014
Problem: Longest Valid Parentheses
Difficulty: Easy
Source: https://oj.leetcode.com/problems/longest-valid-parentheses/
Notes:
Given a string containing just the characters '(' and ')', find the length of the longest valid
(well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()",
which has length = 4.
Solution: O(n).
*/
public class Solution {
public int longestValidParentheses_1(String s) {
Stack<Integer> stk = new Stack<Integer>();
int res = 0, count = 0;
for(int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '(') {
stk.push(count);
count = 0;
} else if (stk.empty() == false) {
count += (1 + stk.pop());
res = Math.max(res, count);
} else {
count = 0;
}
}
return res * 2;
}
public int longestValidParentheses_2(String s) {
int n = s.length();
if (n <= 1) return 0;
int res = 0;
int[] f = new int[n];
for(int i=n-2;i>=0;i--){
int match = i + f[i+1] + 1;
if(match<n&&s.charAt(i)=='('&&s.charAt(match)==')'){
f[i]=f[i+1]+2;
if(match+1<n) f[i]+=f[match+1];
}
res = Math.max(res,f[i]);
}
return res;
}
public int longestValidParentheses(String s) {
int counter = 0, val = 0, res = 0;
for (int i = 0; i < s.length(); ++i) {
counter += s.charAt(i) == '(' ? 1 : -1;
if (counter < 0) {
val = counter = 0;
continue;
}
val += s.charAt(i) == '(' ? 0 : 2;
res = counter == 0 ? Math.max(res, val) : res;
}
val = counter = 0;
for (int i = s.length() - 1; i >= 0; --i) {
counter += s.charAt(i) == ')' ? 1 : -1;
if (counter < 0) {
val = counter = 0;
continue;
}
val += s.charAt(i) == ')' ? 0 : 2;
res = counter == 0 ? Math.max(res, val) : res;
}
return res;
}
}