-
Notifications
You must be signed in to change notification settings - Fork 62
/
ValidParentheses.java
69 lines (63 loc) · 1.77 KB
/
ValidParentheses.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
package datastructure.stack.leetcode;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* @author roseduan
* @time 2020/9/9 11:34 下午
* @description 判断有效的括号
*/
public class ValidParentheses {
/**
* 第一种解法:暴力求解,每次进行替换,需要注意退出循环的条件
* 运行结果:速度击败 5%
*/
public boolean isValid1(String s) {
while (s.length() != 0) {
int len = s.length();
s = s.replace("()", "").replace("[]", "").replace("{}", "");
if (s.length() == len){
break;
}
}
return s.length() == 0;
}
/**
* 借助栈实现匹配
*/
public boolean isValid2(String s) {
Map<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (stack.empty() || !map.get(c).equals(stack.pop())) {
return false;
}
}
return stack.empty();
}
/**
* 另一种写法
*/
public boolean isValid3(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else {
if (stack.empty() || stack.pop() != c) {
return false;
}
}
}
return stack.empty();
}
}