专栏首页五分钟学算法两分钟看懂有效的括号

两分钟看懂有效的括号

大家好,我是程序员吴师兄,今天跟大家分享一道和 有关的题目,超级简单也超级容易理解,这道题目曾经出现在 bilibili 的面试中。

一、题目描述

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

有效字符串需满足:

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。

示例 1:

输入:s = "()"
输出:true

示例 2:

输入:s = "([)]"
输出:false

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

二、题目解析

我们用 四步分析法 来分析一下这道题目。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1.模拟

有效的情况:

1)不嵌套

2)嵌套

无效的情况:

1)长度为奇数,左括号多余

2)长度为奇数,右括号多余

3)长度为偶数,左括号与右括号不配对

4)长度为偶数,部分子表达式可以配对,但外部不配对

2.规律

通过上述的模拟,可以总结出以下 3 个特点:

  • 1、([]{} 是一一对应的关系,无法配对是无效的
  • 2、对于有效的括号,它的部分子表达式仍然是有效的括号,比如 { [ ( ) ]} ,如果部分子表达式无效,那么整体都是无效的
  • 3、部分子表达式如果建立了配对关系,是有效的括号,那么 消除 后是不会影响整体的
  • 4、奇数长度的字符串总是无效的。

3.匹配

整个过程分为两步,一个是配对,一个是消除。

配对 过程,[]{}

消除 的过程是由内向外进行,先判断能否消除部分子表达式(内),再判断能否消除整体表达式(外),但在遍历的过程却是由外向内进行遍历,需要保存状态, 先进后出的特点符合要求。

4.边界

所谓边界,即特殊情况:

  • 字符串的长度为奇数

三、动画图解

四、参考代码

// 登录 https://www.algomooc.com 查看更多图解
class Solution {
    
    public boolean isValid(String s) {
        // 当字符串长度为奇数的时候,属于无效情况
        // 条件说明了长度至少为 1,所以不需要在判空
      if (s.length() % 2 == 1) {
         return false;
       }
       
       //构建栈
        Stack<Character> stack = new Stack<Character>();
        
        //由外向内遍历字符串
        for(char c : s.toCharArray()){
            
            if(c == '('){
               stack.push(')');
            }else if(c == '['){
               stack.push(']');
            }else if( c == '{'){
               stack.push('}');
            }else if( stack.isEmpty() || c != stack.pop()){
            //表明有多余的括号
               return false;
            }
        }
        return stack.isEmpty();
    }
}

五、复杂度分析

时间复杂度

时间复杂度为 O(N)。需要遍历一遍字符串。

空间复杂度

空间复杂度 O(N)。最坏情况下,栈的大小将是输入字符串的长度。

六、参考引用

1、https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/

2、https://t10.lagounews.com/aR44RbR+c190C

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员吴师兄

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-03-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 与栈有关:3 分钟看懂如何判断括号的合法性

    对括号的合法性判断是一个很常见且实用的问题,比如说我们写的代码,编辑器和编译器都会检查括号是否正确闭合。而且我们的代码可能会包含三种括号[](){},判断起来有...

    五分钟学算法
  • 3 分钟看懂如何判断括号的合法性

    对括号的合法性判断是一个很常见且实用的问题,比如说我们写的代码,编辑器和编译器都会检查括号是否正确闭合。而且我们的代码可能会包含三种括号[](){},判断起来有...

    乔戈里
  • 力扣 (LeetCode)-两数之和,有效的括号,两数相加

    每天学习编程,让你离梦想更新一步,感谢不负每一份热爱编程的程序员,不论知识点多么奇葩,和我一起,让那一颗四处流荡的心定下来,一直走下去,加油,2021加油!欢迎...

    达达前端
  • LeetCode 1111. 有效括号的嵌套深度(奇偶分离)

    给你一个有效括号字符串 seq,将其分成两个不相交的子序列 A 和 B,且 A 和 B 满足有效括号字符串的定义(注意:A.length + B.length ...

    Michael阿明
  • 3分钟看懂Python后端必须知道的Django的信号机制

    django自带一套信号机制来帮助我们在框架的不同位置之间传递信息。也就是说,当某一事件发生时,信号系统可以允许一个或多个发送者(senders)将通知或信号(...

    砸漏
  • 云+社区海外技术视频引进计划

    云加社区是腾讯云官方开发者社区。致力于为开发者服务,分享技术干货,扩大技术影响力,打造纯粹的开发者技术平台。云加社区具兼具文章分享、问答社区、清单建设、视频分享...

    云加社区
  • System Generator系列之多速率系统的使用(上)

    玩FPGA的都知道,跨时钟域进行处理设计是很常见的事,而常见的有使用FIFO或者双口RAM实现跨时钟域的数据传输,再进而处理,本次将讲一下在System Gen...

    狂人V
  • 【LeetCode第 161 场周赛】回顾

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 从IIC实测波形入手,搞懂IIC通信

    玩单片机的朋友都知道IIC通信这个工具,但好多人只是会用,内部的原理不求甚解,或是想要了解其原理,但却对抽象的时序描述一头雾水。本文将从实测的IIC波形入手,带...

    xxpcb
  • 基于basys2驱动LCDQC12864B的verilog设计图片显示

      话不多说先上图 ? 前言        在做这个实验的时候在网上找了许多资料,都是关于使用单片机驱动LCD显示,确实用单片机驱动是要简单不少,记得在FPGA...

    NingHeChuan
  • IP CORE 之 PLL- ISE 操作工具

    本系列将带来FPGA的系统性学习,从最基本的数字电路基础开始,最详细操作步骤,最直白的言语描述,手把手的“傻瓜式”讲解,让电子、信息、通信类专业学生、初入职场小...

    FPGA技术江湖
  • STM32入门培训

    比如智能家居、智慧农业、工厂自动化这些,都可以使用STM32作为主控制器或者辅助控制器。

    小锋学长
  • 【图解】记一次手撕算法面试:字节跳动的面试官把我四连击了

    字节跳动这家公司,应该是所有秋招的公司中,对算法最重视的一个了,每次面试基本都会让你手撕算法,今天这篇文章就记录下当时被问到的几个算法题,并且每个算法题我都详细...

    帅地
  • 【图解】记一次手撕算法面试:字节跳动的面试官把我四连击了

    字节跳动这家公司,应该是所有秋招的公司中,对算法最重视的一个了,每次面试基本都会让你手撕算法,今天这篇文章就记录下当时被问到的几个算法题,并且每个算法题我都详细...

    五分钟学算法
  • 【图解】记一次手撕算法面试:字节跳动的面试官把我四连击了

    字节跳动这家公司,应该是所有秋招的公司中,对算法最重视的一个了,每次面试基本都会让你手撕算法,今天这篇文章就记录下当时被问到的几个算法题,并且每个算法题我都详细...

    乔戈里
  • 阿里技术一面,Java研发岗

    之前过了个简单的简历面,过了几天后没打来以为凉了,然后昨晚又接到了电话,括号内容是回答说的,理解有限,不一定都对,欢迎纠正~加油每一个牛友们! 阿里一面: ...

    牛客网
  • 为什么真正聪明的人都是概率高手?(零公式入门篇)

    这或者是因为他们小时候的生活环境是个天然的概率训练场,或者是因为大脑本身就是一个概率机器。

    华章科技
  • 教你如何通过分析GC日志来进行JVM调优

    不同的垃圾收集器产生的GC日志大致遵循了同一个规则,只是有些许不同,不过对于G1收集器的GC日志和其他垃圾收集器有较大差别,话不多说,正式进入正文。。。

    肉眼品世界
  • 这里有 300 篇 Python 与机器学习类原创笔记

    主要包括计算机科学中基本的算法与数据结构,结合算法思想和Leetcode实战,总结介绍。

    好好学java

扫码关注云+社区

领取腾讯云代金券