Question
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
1
2
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
대충 해석
괄호가 쌍으로 잘 열고 닫혀있는지 판단해보세요. 한 쪽만 있거나 열고 닫고의 괄호 짝이 맞지 않으면 안 됩니다.
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#1
Input: s = "()"
Output: true
#2
Input: s = "([)]"
Output: false
#3
Input: s = "(]"
Output: false
#4
Input: s = "{[]}"
Output: true
Solution
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
import java.util.Stack;
public class ValidParentheses {
public static void main(String[] args) {
// LeetCode Easy 20
String s ="())";
int len = s.length();
boolean flag = isValidParentheses(s, len);
System.out.println(flag);
}
public static boolean isValidParentheses(String s, int len) {
boolean flag = false;
System.out.println("string => " + s);
if(len % 2 == 0) {
Stack<Character> stack = new Stack<>();
for(int i = 0; i < len; i ++) {
char c = s.charAt(i);
if(isLeft(c) > 0) {
stack.push(c);
} else {
if(!stack.empty()) {
char pop = stack.pop();
if(isLeft(pop) != isRight(c)) {
return false;
}
} else {
return false;
}
}
}
flag = stack.isEmpty();
}
return flag;
}
public static int isLeft(char c) {
int isValid = 0;
switch(c) {
case '(' : isValid = 1; break;
case '{' : isValid = 2; break;
case '[' : isValid = 3; break;
}
return isValid;
}
public static int isRight(char c) {
int isValid = 0;
switch(c) {
case ')' : isValid = 1; break;
case '}' : isValid = 2; break;
case ']' : isValid = 3; break;
}
return isValid;
}
}