写点什么

【刷题记录】20. 有效的括号

作者:WangNing
  • 2022 年 7 月 24 日
  • 本文字数:965 字

    阅读完需:约 3 分钟

一、题目描述

来源:力扣(LeetCode)


给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。


有效字符串需满足:


  • 左括号必须用相同类型的右括号闭合。

  • 左括号必须以正确的顺序闭合。


示例 1:


输入:s = "()"输出:true
复制代码


示例 2:


输入:s = "()[]{}"输出:true
复制代码


示例 3:


输入:s = "(]"输出:false
复制代码


示例 4:


输入:s = "([)]"输出:false
复制代码


示例 5:


输入:s = "{[]}"输出:true
复制代码


提示:


  • 1 <= s.length <= 104

  • s 仅由括号 '()[]{}' 组成

二丶思路分析

使用栈来解决在这道题目中,我们遍历时候,每个左括号,都要对应一个相应的右括号,而且后面出现的左括号要优先匹配,这个跟栈 先进后出 是十分类似的。


  • 当遇到左括号时候,入栈

  • 当遇到右括号时候,取出栈顶括号

  • 判断出去括号 是否跟右括号类型一致,不一致,直接返回false

  • 如果栈中没有左括号了,也直接返回 false

  • 当遍历完所有的字符串

  • 栈为空,说明所有的括号都闭合了

  • 栈不为空,说明还有括号没有匹配闭合

  • 当匹配的时候,字符串长度一定为偶数,否则肯定不匹配,直接返回 false

  • 为了方便匹配,我们可以用哈希表存储每一种括号。键为右括号,值为相同类型的左括号。

三、代码实现

class Solution {    public boolean isValid(String s) {        int length = s.length();        if (length % 2 != 0) {            return false;        }
Map<Character, Character> map = new HashMap<Character, Character>() {{ put(')', '('); put(']', '['); put('}', '{'); }}; Deque<Character> stack = new LinkedList<Character>(); for (int i = 0; i < length; i++) { char ch = s.charAt(i); if (map.containsKey(ch)) { if (stack.isEmpty() || stack.peek() != map.get(ch)) { return false; } stack.pop(); } else { stack.push(ch); } } return stack.isEmpty(); }}
复制代码

复杂度分析

时间复杂度:,其中 n 是字符串 s 的长度。


空间复杂度:复杂度为 ,使用哈希表的空间

运行结果


总结

有些问题,我们可以使用有类似特性的数据结构来处理,可以帮我们更快的解决问题。

发布于: 4 小时前阅读数: 15
用户头像

WangNing

关注

还未添加个人签名 2020.10.13 加入

一个只想提(快)升(乐)自(摸)我(鱼)的混子选手~

评论

发布
暂无评论
【刷题记录】20. 有效的括号_7月月更_WangNing_InfoQ写作社区