-
Notifications
You must be signed in to change notification settings - Fork 1
/
ValidParenthesis.java
138 lines (128 loc) · 4.42 KB
/
ValidParenthesis.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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/**
* Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
*
* The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
*/
package com.alg.leetup;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* @author rbaral
*
*/
public class ValidParenthesis {
private static DateFormat format = new SimpleDateFormat("YYYY-M-d:H:m:s:S");
/**
* @param args
*/
public static void main(String[] args) {
boolean isTestMode = true;
if (isTestMode) {
performTest();
} else {
String s = "[";
s = "([])";
System.out.println(format.format(new Date()));
System.out.println(isValid(s));
System.out.println(format.format(new Date()));
}
}
/**
* we first check for simple base cases for other cases, we push each
* character to a list and check if the next character to be pushed forms a
* pair with the last pushed char. If found, we remove the last pushed char,
* else, we keep on pushing. If at the end, the list is empty, it means we
* have found pair for all the chars and we return true else we return false
*
* @param s
* @return
*/
public static boolean isValid(String s) {
//base case
if (s == null || s.length() < 2) {
return false;
} else if (s.length() == 2) {
return isPair(s.charAt(0), s.charAt(1));
} else if (s.length() % 2 != 0)//has odd characters
{
return false;
} else {
System.out.println("checking for:" + s);
// push the remaining characters to the the list and while pushing check if consecutives form a pair
List<String> charsList = new ArrayList<String>();
for (int i = 0; i < s.length(); i++) {
if (i == 0 || charsList.isEmpty()) {
charsList.add(String.valueOf(s.charAt(i)));
} else// check if the last one and this form a pair
if (isPair(charsList.get(charsList.size() - 1).charAt(0), s.charAt(i))) {
// remove the last entry from list
charsList.remove(charsList.size() - 1);
} else {
charsList.add(String.valueOf(s.charAt(i)));
}
}
if (charsList.size() == 0) {
return true;
} else {
return false;
}
}
}
public static boolean isPair(char a, char b) {
if (a == '(' && b == ')') {
return true;
}
if (a == '{' && b == '}') {
return true;
}
if (a == '[' && b == ']') {
return true;
}
return false;
}
public static char getPair(char a) {
char result = a;
switch (a) {
case '(':
result = ')';
break;
case '{':
result = '}';
break;
case '[':
result = ']';
break;
default:
result = a;
}
return result;
}
public static void performTest() {
Map<String, Boolean> testCases = new HashMap<String, Boolean>();
List<String> failedCases = new ArrayList<String>();
testCases.put("[", Boolean.FALSE);
testCases.put("(]", Boolean.FALSE);
testCases.put("([)]", Boolean.FALSE);
testCases.put("()", Boolean.TRUE);
testCases.put("()[]{}", Boolean.TRUE);
testCases.put("{[{}]}", Boolean.TRUE);
testCases.put("{[{}]}{[{}]}", Boolean.TRUE);
testCases.put("([])", Boolean.TRUE);
boolean result = false;
for (String testCase : testCases.keySet()) {
result = isValid(testCase);
if (testCases.get(testCase) != result) {
failedCases.add("Failed for:" + testCase + " expected:" + testCases.get(testCase) + " got:" + result);
}
}
System.out.println("TEST RESULT: PASSED:" + (testCases.size() - failedCases.size()) + " FAILED:" + failedCases.size());
for (String s : failedCases) {
System.err.println(s);
}
}
}