leetcode-java/src/ValidParentheses20.java at master · fluency03/leetcode-java · GitHub

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
/**
 * 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.
 */


importjava.util.Map;
importjava.util.HashMap;
importjava.util.Stack;


publicclassValidParentheses20 {
publicbooleanisValid(Strings) {
char[] chars = s.toCharArray();

Stackst = newStack();

for (charc: chars) {

if (isBackP(c)) {
if (st.empty()) {
returnfalse;
 } else {
chartop = (char) st.pop();
if (c != top) {
returnfalse;
 }
 }
 } else {
st.push(pair(c));
 }
 }

returnst.empty();
 }

privatebooleanisBackP(charc) {
returnc == '}' || c == ']' || c == ')';
 }

privatecharpair(charc) {
if (c == '{') {
return'}';
 } elseif (c == '[') {
return']';
 } else {
return')';
 }
 }


/**
 * https://discuss.leetcode.com/topic/27572/short-java-solution
 */
publicbooleanisValid2(Strings) {
Stack<Character> stack = newStack<Character>();
for (charc : s.toCharArray()) {
if (c == '(')
stack.push(')');
elseif (c == '{')
stack.push('}');
elseif (c == '[')
stack.push(']');
elseif (stack.isEmpty() || stack.pop() != c)
returnfalse;
 }
returnstack.isEmpty();
 }


publicbooleanisValid3(Strings) {
if (s == null || s.length()%2 == 1) returnfalse;
if (s.length() == 0) returntrue;

Stack<Character> st = newStack<>();
for (charc : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
continue;
 }

if (st.isEmpty()) returnfalse;

switch (c) {
case')':
if (st.peek() == '(') {
st.pop();
break;
 } else {
returnfalse;
 }
case']':
if (st.peek() == '[') {
st.pop();
break;
 } else {
returnfalse;
 }
case'}':
if (st.peek() == '{') {
st.pop();
break;
 } else {
returnfalse;
 }
default: returnfalse;
 }

 }

returnst.isEmpty();
 }


publicstaticvoidmain(String[] args) {
ValidParentheses20vp = newValidParentheses20();

System.out.println(vp.isValid("["));
System.out.println(vp.isValid("]"));
System.out.println(vp.isValid("[]"));
 }

}