【力扣刷题】20. 有效的括号
一、题目描述
来源:力扣（LeetCode）
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true示例 2：
输入：s = "()[]{}"
输出：true示例 3：
输入：s = "(]"
输出：false示例 4：
输入：s = "([)]"
输出：false示例 5：
输入：s = "{[]}"
输出：true提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
二、思路分析
- 首先建立一个哈希表来存储每种右边括号的配对，然后新建一个栈
- 碰到左边括号的，入栈
- 碰到右边括号的，判断是否为空，并且与栈顶判断是否与之对应的左括号，是的话，左括号出栈，不是的话，右括号入栈
- 最后如果栈为空的话就是有效的括号 图示如下(图在leetCode复制的，比较清晰)：
image.png
baa8829ac398e665eb645dca29eadd631e2b337e05022aa5a678e091471a4913-20.gif
三、代码实现
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();
}
}四、运行结果
image.png
总结
当开始接触题目时，我们会不禁想到如果计算出左括号的数量，和右括号的数量，如果每种括号左右数量相同，会不会就是有效的括号了呢？
事实上不是的，假如输入是 [{]}，每种括号的左右数量分别相等，但不是有效的括号。这是因为结果还与括号的位置有关。而栈先入后出特点恰好与本题括号排序特点一致，，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-03-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录