-
-
Notifications
You must be signed in to change notification settings - Fork 297
/
Copy path20.java
139 lines (136 loc) · 4.05 KB
/
20.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
139
__________________________________________________________________________________________________
0ms
class Solution {
public boolean isValid(String s) {
char stack[] = new char[s.length()];
int top = -1;
char current;
for(int i = 0; i < s.length(); i++)
{
current = s.charAt(i);
if(current =='(' || current =='[' || current == '{'){
stack[++top] = current;
}
else
{
if(top == -1)
return false;
else if(current == ')' && stack[top] != '(')
return false;
else if(current == ']' && stack[top] != '[')
return false;
else if(current == '}' && stack[top] != '{')
return false;
else
top--;
}
}
if(top == -1)
return true;
return false;
}
}
__________________________________________________________________________________________________
1ms
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.isEmpty();
}
}
__________________________________________________________________________________________________
2ms
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for(int i=0; i<s.length(); i++) {
if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
stack.push(s.charAt(i));
} else {
if(stack.empty()) {
return false;
}
Character val = stack.pop();
// System.out.println(val);
if(!((val == '(' && s.charAt(i) == ')') || (val == '[' && s.charAt(i) == ']') || (val == '{' && s.charAt(i) == '}'))) {
return false;
}
}
}
if(stack.empty()) {
return true;
} else {
return false;
}
}
}
__________________________________________________________________________________________________
34152 kb
class Solution {
public boolean isValid(String s) {
if (s.isEmpty())
return true;
Map<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
Stack<Character> stack = new Stack<>();
if (s.length() % 2 != 0)
return false;
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
// close
if (stack.isEmpty())
return false;
Character c = stack.pop();
if (map.get(s.charAt(i)) != c) {
return false;
}
}
if(map.containsValue(s.charAt(i))){
//open
stack.add(s.charAt(i));
continue;
}
}
if(!stack.isEmpty())
return false;
return true;
}
}
__________________________________________________________________________________________________
34236 kb
class Solution {
public boolean isValid(String s) {
Map<String, String> CoupleString = new HashMap<String, String>();
CoupleString.put(")","(");
CoupleString.put("}","{");
CoupleString.put("]","[");
Stack<String> aCharStringStack = new Stack<String>();
aCharStringStack.empty();
for(int i =0;i<s.length();i++){
String aCharStr = s.substring(i,i+1);
if(!aCharStringStack.isEmpty()){
String aCharOfStack = aCharStringStack.pop();
if(!aCharOfStack.equals(CoupleString.get(aCharStr))){
aCharStringStack.push(aCharOfStack);
aCharStringStack.push(aCharStr);
}
}else {
aCharStringStack.push(aCharStr);
}
}
return aCharStringStack.empty();
}
}
__________________________________________________________________________________________________