leetcode20-有效的括号(栈+HashMap)
2021/7/13 23:36:03
本文主要是介绍leetcode20-有效的括号(栈+HashMap),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
解题思路
【算法原理】
-
栈先入后出特点恰好与本题括号排序特点一致,即若遇到左括号入栈,遇到右括号时将对应栈顶左括号出栈,则遍历完所有括号后 stack 仍然为空;
-
建立哈希表 pairs 构建左右括号对应关系:key 左括号,value 右括号;这样查询 2 个括号是否对应只需 O(1) 时间复杂度;建立栈 stack,遍历字符串 s 并按照算法流程判断。
【算法流程】
-
如果 ch 是左括号,则入栈 push;
-
否则通过哈希表判断括号对应关系,若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 ch 不对应,则提前返回 false。
【代码】
public class Solution { public boolean isValid(String s) { int len = s.length(); //奇数 if (len % 2 == 1) { return false; } //括号键值对 Map<Character, Character> pairs = new HashMap<Character, Character>() {{ put(')', '('); put(']', '['); put('}', '{'); }}; //队列 Deque<Character> stack = new LinkedList<Character>(); for (int i = 0; i < len; i++) { char ch = s.charAt(i); if (pairs.containsKey(ch)) { //栈中是否存在对应括号 if (stack.isEmpty() || stack.peek() != pairs.get(ch)) { //判断栈顶与当前是否相等 return false; } stack.pop(); //存在,出栈 } else { stack.push(ch); //入栈 } } return stack.isEmpty(); } public static void main(String[] args) { System.out.println(new Solution().isValid("()[]{}")); } }
这篇关于leetcode20-有效的括号(栈+HashMap)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享