20. 有效的括号
题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例
输入: "()"
输出: true
输入: "()[]{}"
输出: true
输入: "(]"
输出: false
输入: "([)]"
输出: false
输入: "{[]}"
输出: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
我的方案
利用List存储首次出现的左侧符号。 遇到右侧符号时，与Lizt最后一项进行比较，不符合就返回 false 全部匹配完，返回 list的长度==0的判断值。
Java源码
public boolean isValid(String s) {
List<Character> left = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '[' || c == '{' || c == '(') {
left.add(c);
} else {
if (left.size() == 0)
return false;
if (c == ']' && left.get(left.size() - 1) != '[')
return false;
if (c == '}' && left.get(left.size() - 1) != '{')
return false;
if (c == ')' && left.get(left.size() - 1) != '(')
return false;
left.remove(left.size() - 1);
}
}
return left.size() == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Dart源码
List<String> left = [];
for (int i = 0; i < s.length; i++) {
String c = s.substring(i, i + 1);
if (c == '[' || c == '{' || c == '(') {
left.add(c);
} else {
if (left.length == 0) return false;
if (c == ']' && left[left.length - 1] != '[') return false;
if (c == '}' && left[left.length - 1] != '{') return false;
if (c == ')' && left[left.length - 1] != '(') return false;
left.removeAt(left.length - 1);
}
}
return left.length == 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
推荐方案
思路类似，不过他是用数组+最后位下标配合使用
Java源码
public boolean isValid(String s) {
char[] stack = new char[s.length()+1];
int top = 1;
for(char c : s.toCharArray()){
if(c == '(' || c == '{' || c == '['){
stack[top++] = c;
}else if(c == ')' && stack[--top] != '('){
return false;
}else if(c == '}' && stack[--top] != '{'){
return false;
}else if(c == ']' && stack[--top] != '['){
return false;
}
}
return top == 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16