-
Notifications
You must be signed in to change notification settings - Fork 4
/
LongestValidParentheses.java
93 lines (87 loc) · 2.83 KB
/
LongestValidParentheses.java
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package string;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
/**
* Given a string containing just the characters '(' and ')', find the
* length of the longest valid (well-formed) parentheses substring.
*
* E.g.
* Input: ")()())"
* Output: 4
* Explanation: The longest valid parentheses substring is "()()"
*
* @author ruifengm
* @since 2018-May-12
*/
public class LongestValidParentheses {
/**
* Use the stack data structure
*/
public static int stackGetLongestValidParenLen(String s) {
ArrayList<Boolean> list = new ArrayList<>(); // boolean value list indicating parenthesis match/unmatch in order
Stack<Integer> stack = new Stack<>(); // storing indices of '(' in the list
for (char c: s.toCharArray()) {
if (c=='(') {
list.add(new Boolean(false)); // '(' not matched
stack.push(list.size()-1); // current index of '(' to be matched
}
if (c==')') {
if (!stack.isEmpty()) { // able to match
list.set(stack.pop(), new Boolean(true)); // '(' matched
list.add(new Boolean(true)); // ')' matched
} else list.add(new Boolean(false)); // ')' not matched
}
//System.out.println(list.toString());
}
// Iterate through the list to look for longest continuous 'true' sequence
int max = 0;
int count = 0;
for (int i=0; i<list.size(); i++) {
if (list.get(i).equals(true)) count++;
else {
if (count > max) max = count;
count = 0;
}
}
if (count > max) max = count;
return max;
}
/**
* Use a DP lookup array.
* Check for patterns like '()()' and '(())' and accumulate the lengths accordingly.
*
* E.g. for string "( ) ( ) ( ( ) )"
* the DP lookup array is [0, 2, 0, 4, 0, 0, 2, 8]
*/
private static int DPGetLongestValidParenLen(String s) {
int[] dp = new int[s.length()];
char[] sArr = s.toCharArray();
int maxCount = 0;
for (int i=1; i<sArr.length; i++) {
if (sArr[i] == ')') {
if (sArr[i-1] == '(') dp[i] = 2 + (i>1 ? dp[i-2] : 0); // check for matches like '()()'
else if (i>=dp[i-1]+1 && sArr[i-dp[i-1]-1] == '(') // check for matches like '(())'
dp[i] = dp[i-1] + 2 + (i>=dp[i-1]+2 ? dp[i-dp[i-1]-2] : 0);
maxCount = Math.max(maxCount, dp[i]);
}
}
//System.out.println(Arrays.toString(dp));
return maxCount;
}
public static void main(String[] args) {
// String s = "";
// String s = "((((((";
// String s = "))))";
// String s = "((()())";
// String s = ")()())";
// String s = "(This(is(a(test)string)to)use)";
// String s = "())()";
// String s = "()(()";
// String s = "()(())";
// String s = "()()(())";
String s = "(()()))(()()()())";
System.out.println("Length of longest valid parentheses substring: " + stackGetLongestValidParenLen(s));
System.out.println("Length of longest valid parentheses substring: " + DPGetLongestValidParenLen(s));
}
}