-
Notifications
You must be signed in to change notification settings - Fork 13
/
Copy pathSolution0020.java
52 lines (48 loc) · 1.62 KB
/
Solution0020.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
// 20. 有效的括号
/*
思路:
1、括号有序,即使多层嵌套也必然至少有一对相邻有序出现,从内部逐层抵消
2、使用while循环判断字符串的相邻有序对
*/
class Solution {
public boolean isValid(String s) {
while (s.contains("()") || s.contains("{}") || s.contains("[]")) {
if (s.contains("()")) {
s = s.replace("()", "");
}
if (s.contains("{}")) {
s = s.replace("{}", "");
}
if ( s.contains("[]")) {
s = s.replace("[]", "");
}
}
return s.isEmpty();
}
}
/*
思路:
1、使用HashMap存放括号对,方便映射获取
2、由括号的顺序特点,使用栈存放左括号,以后进先出的方式与右括号抵消
3、字符串使用for循环遍历处理每个字符,维护一个栈,碰到左括号就入栈,碰到右括号则取出栈顶元素,判断栈顶元素和右括号是否匹配
4、栈为空或括号不匹配,则为false,否则true
*/
class Solution {
public boolean isValid(String s) {
HashMap<Character, Character> map = new HashMap<Character, Character>() {{
put('(', ')');
put('{', '}');
put('[', ']');
}};
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
stack.push(c);
} else if (stack.isEmpty() || map.get(stack.pop()) != c) {
return false;
}
}
return stack.isEmpty();
}
}