【Leetcode 热题 100】20. 有效的括号

问题背景

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串$s$，判断字符串是否有效。
有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 每个右括号都有一个对应的相同类型的左括号。

数据约束

• $1\le s.length\le 10^4$
• $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();}
}