当前位置: 首页 > news >正文

LeetCode20:有效的括号

原题地址:. - 力扣(LeetCode)

题目描述

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"

输出:true

示例 2:

输入:s = "()[]{}"

输出:true

示例 3:

输入:s = "(]"

输出:false

示例 4:

输入:s = "([])"

输出:true

提示:

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

解题思路

  • 输入检查:首先检查输入字符串是否为空或长度为零。如果是,则返回 true,表示有效。
  • 长度检查:如果字符串的长度小于等于 1 或者是奇数,直接返回 false,因为无法匹配成对的括号。
  • 使用栈:创建一个栈来存放左括号。遍历字符串中的每个字符:
    • 如果当前字符是左括号 ([ 或 {,将其压入栈中。
    • 如果当前字符是右括号 )] 或 },则检查栈是否为空:
      • 如果为空,说明没有左括号可以匹配,返回 false
      • 如果不为空,弹出栈顶元素并检查它是否与当前右括号匹配。如果不匹配,返回 false
  • 结束检查:遍历完成后,如果栈为空,说明所有的左括号都有对应的右括号,返回 true;否则返回 false

源码实现

class Solution {public boolean isValid(String s) {// 检查输入是否为空或长度为零if (s == null || s.length() == 0) {return true; // 空字符串被认为是有效的}// 检查长度是否小于等于1或为奇数if (s.length() <= 1 || s.length() % 2 != 0) {return false; // 不能成对匹配}// 创建一个栈来存放左括号Stack<Character> stack = new Stack<Character>();// 遍历字符串中的每个字符for (char c : s.toCharArray()) {// 如果是左括号,压入栈中if (c == '(' || c == '[' || c == '{') {stack.push(c);continue;}// 如果是右括号,检查栈是否为空if (stack.isEmpty()) {return false; // 没有对应的左括号}// 检查栈顶元素是否匹配if (c == ')' && stack.pop() != '(') {return false; // 不匹配} else if (c == ']' && stack.pop() != '[') {return false; // 不匹配} else if (c == '}' && stack.pop() != '{') {return false; // 不匹配}}// 如果栈为空,所有括号都匹配,返回true;否则返回falsereturn stack.isEmpty();}
}

复杂度分析

  • 时间复杂度:O(n),其中 n 是字符串的长度。我们只需遍历字符串一次,栈的入栈和出栈操作的时间复杂度为 O(1)。
  • 空间复杂度:O(n),在最坏的情况下,栈中可能会存放所有的左括号(例如字符串为 "((("),因此需要 O(n) 的空间。

http://www.mrgr.cn/news/62746.html

相关文章:

  • 如何在短时间内入门并掌握深度学习?
  • SSL/TLS 密码套件漏洞分析以及修复方法
  • 理解 Vue 的单向数据流
  • 如何查看磁盘的类型?(固态硬盘 or 机械硬盘)
  • 块设备驱动的基本概念
  • 【Python各个击破】numpy
  • 支持ANC的头戴式蓝牙耳机,更有小金标认证,QCY H3 Pro体验
  • 10.30
  • AR基础知识:SLAM同时定位和构图
  • 功能强大视频编辑软件 Movavi Video Editor Plus 2024 v24.2.0 中文特别版
  • ValueError: Object arrays cannot be loaded when allow_pickle=False
  • Typora配置GitHub图床--结合PicGo
  • 配置DDNS结合光猫路由器实现外网映射
  • SAP 采购申请的增强(对内容的处理,比如批次)
  • MySQL的使用
  • 亚马逊云免费Amazon CloudFront服务
  • 基于单片机的无线气象仪系统设计(论文+源码)
  • 程序员工作七年,我踩过的那七个坑
  • 好的呼叫中心系统是什么样的
  • Postman中的API安全堡垒:全面安全性测试指南_postman安全测试
  • 命名空间是啥意思
  • 10 大开源无头浏览器推荐:自动化测试、爬虫与 RPA 的强大助手
  • SpringBoot+Shiro权限管理
  • [ 应急响应靶场实战 ] VMware 搭建win server 2012应急响应靶机 攻击者获取服务器权限上传恶意病毒 防守方人员应急响应并溯源
  • 信息管理与信息系统专业的建设与发展 ——人才培养模式探讨
  • shell基础-case