来源:力扣(LeetCode)
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
示例 4:
输入:s = "([)]"
输出:false
示例 5:
输入:s = "{[]}"
输出:true
提示:
1 <= s.length <= 104
s
仅由括号 '()[]{}'
组成class Solution {
public boolean isValid(String s) {
//建立左右括号配对
Map<Character,Character> map = new HashMap<>();
map.put(')','(');
map.put(']','[');
map.put('}','{');
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
//如果遇到右边的括号,否则进栈
if(map.containsKey(c)){
//判断栈顶是否匹配,不匹配push进栈
if(!stack.isEmpty() && stack.peek().equals(map.get(c))){
stack.pop();
}else{
stack.push(c);
}
}else{
stack.push(c);
}
}
return stack.isEmpty();
}
}
当开始接触题目时,我们会不禁想到如果计算出左括号的数量,和右括号的数量,如果每种括号左右数量相同,会不会就是有效的括号了呢?
事实上不是的,假如输入是 [{]}
,每种括号的左右数量分别相等,但不是有效的括号。这是因为结果还与括号的位置有关。而栈先入后出特点恰好与本题括号排序特点一致,,即若遇到左括号入栈,遇到右括号时将对应栈顶左括号出栈,则遍历完所有括号后 stack
仍然为空;