-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy pathWellNestedOpenClose.java.off
More file actions
80 lines (73 loc) · 2.05 KB
/
WellNestedOpenClose.java.off
File metadata and controls
80 lines (73 loc) · 2.05 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
73
74
75
76
77
78
79
80
/*
https://leetcode.com/problems/valid-parentheses/
*/
import java.util.Deque;
import java.util.LinkedList;
public class WellNestedOpenClose {
public static char close(char c) {
switch (c) {
case '(':
return ')';
case '[':
return ']';
case '{':
return '}';
default:
throw new IllegalArgumentException(String.valueOf(c));
}
}
public boolean isValid(String s) {
Deque<Character> stack = new LinkedList<>();
int l = s.length();
for (int i = 0; i < l; i++) {
char c = s.charAt(i);
switch (c) {
case '(':
case '[':
case '{':
stack.push(c);
break;
default:
if (stack.isEmpty() || c != close(stack.pop()))
return false;
break;
}
}
if (!stack.isEmpty())
return false;
return true;
}
/*
By using a magic value for characters that don't close,
we can reuse this on the main loop code.
Another saner but less efficient possibility would be to return character / boolean pair,
where the boolean indicates if the char can be closed.
*/
public static char closeMagic(char c) {
switch (c) {
case '(':
return ')';
case '[':
return ']';
case '{':
return '}';
}
return 0;
}
public boolean isValidMagic(String s) {
Deque<Character> stack = new LinkedList<>();
int l = s.length();
for (int i = 0; i < l; i++) {
char c = s.charAt(i);
if (close(c) != 0) {
stack.push(c);
} else {
if (stack.isEmpty() || c != close(stack.pop()))
return false;
}
}
if (!stack.isEmpty())
return false;
return true;
}
}