1，问题描述
20. 有效的括号
难度：简单
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
**输入：**s = “()”
**输出：**true
示例 2：
**输入：**s = “()[]{}”
**输出：**true
示例 3：
**输入：**s = “(]”
**输出：**false
示例 4：
**输入：**s = “([])”
**输出：**true
提示：
1 <= s.length <= 104s 仅由括号 '()[]{}' 组成
2，初步思考
模式识别：分治合并是我首先想到的解法，str是否合规取决于str里面的是否合规，所以直接递归求解解决
官方使用的方法更巧妙，使用的stack栈的解法，入栈准备作为新来数据的匹配项，如果匹配就出栈，继续循环
3，代码处理
第一次的思路想复杂了
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
| import java.util.*;
public class _20有效的括号 {
public boolean isValid_stack(String s) {
if (s == null || s.isEmpty()) {
return true;
}
if (s.length() % 2 != 0) {
return false;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!stack.isEmpty() && getBeforeChar(c) == stack.peek()) {
stack.pop();
} else {
stack.add(c);
}
}
return stack.isEmpty();
}
static Map<String, Boolean> map = new HashMap<>();
public boolean isValid(String s) {
boolean flag = false;
if (map.containsKey(s)) {
return map.get(s);
} else if (s.isEmpty()) {
map.put(s, true);
return true;
} else if (s.length() % 2 != 0 || !setLeft.contains(s.charAt(0)) || !setRight.contains(s.charAt(s.length() - 1))) {
map.put(s, false);
return false;
} else if (getNextChar(s.charAt(0)) == s.charAt(s.length() - 1)) {
flag = isValid(s.substring(1, s.length() - 1));
if (flag) {
map.put(s, true);
return true;
}
}
for (int i = 1; i < s.length() - 1; i = i + 2) {
flag = isValid(s.substring(0, i + 1)) && isValid(s.substring(i + 1, s.length()));
if (flag) {
map.put(s, true);
return true;
}
}
map.put(s, false);
return false;
}
private char getNextChar(char preChar) {
switch (preChar) {
case '(':
return ')';
case '[':
return ']';
case '{':
return '}';
default:
return ' ';
}
}
private char getBeforeChar(char preChar) {
switch (preChar) {
case ')':
return '(';
case ']':
return '[';
case '}':
return '{';
default:
return ' ';
}
}
private static Set<Character> setLeft = null;
private static Set<Character> setRight = null;
static {
setLeft = new HashSet<>();
setLeft.add('(');
setLeft.add('[');
setLeft.add('{');
setRight = new HashSet<>();
setRight.add(')');
setRight.add(']');
setRight.add('}');
}
public static void main(String[] args) {
_20有效的括号 valid = new _20有效的括号();
System.out.println(valid.isValid_stack("{}{{}}"));
}
}
|
官方题解中速度最快的解法，本质与stack栈一致
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
| class Solution {
public boolean isValid(String s) {
char[] s1 = s.toCharArray();
int[] ss = new int[s.length()];
int top = -1,n = s.length();
for(int i = 0;i < n;i ++){
if(s1[i] == '(' || s1[i] == '{' || s1[i] == '['){
ss[++ top] = s1[i];
}
else{
if(s1[i] == ')'){
if(top == -1 || ss[top] != '(')
return false;
top --;
}
else if(s1[i] == '}'){
if(top == -1 || ss[top] != '{')
return false;
top --;
}
else if(s1[i] == ']'){
if(top == -1 || ss[top] != '[')
return false;
top --;
}
}
}
return top == -1;
}
}
|
4，扩展知识
栈stack是你可以把它理解为一个一端封闭的隧道，且宽度只允许一个人
所以会出现，先进后出的情况
5，参考链接
Java Stack 类