【Leetcode 热题 100】20. 有效的括号
问题背景
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串
s
s
s,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
数据约束
- 1 ≤ s . l e n g t h ≤ 1 0 4 1 \le s.length \le 10 ^ 4 1≤s.length≤104
- s s s 仅由括号 ‘()[]{}’ 组成
解题过程
经典括号匹配问题,可以用哈希表来映射左右括号辅助匹配,积累一下双大括号的匿名内部类初始化方式。
单纯写判断效率会更高,栈中要存储的是左括号对应的右括号。
具体实现
哈希映射
class Solution {
public boolean isValid(String s) {
if((s.length() & 1) != 0) {
return false;
}
Map<Character, Character> map = new HashMap<>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()) {
if(!map.containsKey(c)) {
stack.push(c);
} else if(stack.isEmpty() || stack.pop() != map.get(c)) {
return false;
}
}
return stack.isEmpty();
}
}
直接判断
class Solution {
public boolean isValid(String s) {
if((s.length() & 1) != 0) {
return false;
}
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.isEmpty() || stack.pop() != c) {
return false;
}
}
return stack.isEmpty();
}
}