当前位置:网站首页>leetcode 20. Valid Parentheses 有效的括号(中等)
leetcode 20. Valid Parentheses 有效的括号(中等)
2022-08-09 22:10:00 【okokabcd】
一、题目大意
标签: 栈和队列
https://leetcode.cn/problems/valid-parentheses
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1:
输入:s = “()”
输出:true
示例 2:
输入:s = “()[]{}”
输出:true
示例 3:
输入:s = “(]”
输出:false
示例 4:
输入:s = “([)]”
输出:false
示例 5:
输入:s = “{[]}”
输出:true
提示:
- 1 <= s.length <= 104
- s 仅由括号 ‘()[]{}’ 组成
二、解题思路
思路:括号匹配是典型的使用栈来解决的问题。从左向右遍历,每当遇到左括号便放入栈内,遇到右括号则判断其和栈顶的括号是否是统一类型,是则从栈内取出左括号,否则说明字符不串不合法。
实现:遍历字符串,如果栈为空则将当前字符入栈,如果栈顶字符与当前字符匹配则栈顶字符出栈,不匹配当前字符入栈,遍历结束如果栈为空说明字符串合法。
三、解题方法
3.1 Java实现
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (Character c : s.toCharArray()) {
if (isPush(stack, c)) {
stack.push(c);
} else {
stack.pop();
}
}
return stack.isEmpty();
}
private boolean isPush(Stack<Character> stack, Character c) {
if (stack.isEmpty()) {
return true;
}
// {[(
boolean isPop = (stack.peek().equals('[') && c.equals(']') ||
stack.peek().equals('{') && c.equals('}') ||
stack.peek().equals('(') && c.equals(')'));
return !isPop;
}
}
3.2 2014年的实现
public class Solution {
public boolean isValid(String s) {
if (s == null || s.length() == 0) {
return true;
}
Stack<Byte> ps = new Stack<Byte>();
byte[] bArr = s.getBytes();
boolean isValid = true;
for (byte b : bArr) {
if (!isValid) {
break;
}
switch (b) {
case '(':
case '[':
case '{':
ps.push(b);
break;
case ')':
case ']':
case '}':
if (!ps.empty()) {
byte tmpB = ps.pop();
if (tmpB == 40) {
tmpB++;
} else {
tmpB+=2;
}
if (tmpB != b) {
isValid = false;
}
} else {
isValid = false;
}
break;
default:
// do nothing
}
}
if (!ps.empty()) {
isValid = false;
}
return isValid;
}
}
四、总结小记
- 2022/8/9 一场秋雨一场寒
边栏推荐
- What kind of mentality do you need to have when using the stock quantitative trading interface
- Qt message mechanism and events
- tiup cluster template
- 【燃】是时候展现真正的实力了!一文看懂2022华为开发者大赛技术亮点
- 数字与中文大写数字互转(5千万亿亿亿亿以上的数字也支持转换)
- leetcode:286.墙和门
- daemon
- 33. Fabric通道、组织、节点、权限间关系
- UNI-APP_监听页面滚动h5监听页面滚动
- Leetcode 236. 二叉树的最近公共祖先
猜你喜欢
随机推荐
华为云全流程护航《流浪方舟》破竹首发,打造口碑爆款
typedef和#define的花里胡哨的用法
一体化伺服电机在三轴钻孔机中的应用
2022牛客暑期多校训练营6(ABGIJM)
17-GuliMall 搭建虚拟域名访问环境
【技术分享】SLA(服务等级协议)原理与配置
【TS技术课堂】时间序列预测
leetcode:332. 重新安排行程
D. Binary String To Subsequences
五分钟商学院(基础---商业篇)
集合运算样例
Tencent continues to wield the "big knife" to reduce costs and increase efficiency, and free catering benefits for outsourced employees have been cut
Good future, want to be a second new Oriental
少儿编程 电子学会图形化编程等级考试Scratch三级真题解析(判断题)2022年6月
迅为瑞芯微RK3399开发板设置Buildroot文件系统测试MYSQL允许远程访问
OSG笔记:使用setFontResolution设置字体分辨率
Core Data浅谈系列之五 : 在UITableView中展示
友元类和友元函数
B. Neighbor Grid
Leetcode.25 K个一组翻转链表(模拟/递归)