【数据结构与算法】判断字符串是否括号匹配

题目

  • 一个字符串 s 可能包含 { } ( ) [ ] 三种括号
  • 判断 s 是否是括号匹配的
  • 如(a{b}c) 匹配,而 {a(b 或 {a(b}c) 不匹配

  • 先进后出
  • API: push pop length
  • 相关的:队列、堆

栈和数组的关系或区别 

栈是一种逻辑结构,理论模型,不管如何实现,都不受任何语言的限制。

数组是一个物理结构,真实的功能实现,受限于编程语言。

解题思路

  • 遇到左括号 ( [ { 就压入栈
  • 遇到右括号 } ] ) 就判断栈顶,匹配则出栈
  • 最后判断 length 是否为 0

时间复杂度 O(n) 空间复杂度 O(n)

match-bracket.ts

// 括号匹配// 判断左右括号是否匹配
function isMatch(left: string, right: string) {if(left === '{' && right === '}') return trueif(left === '[' && right === ']') return trueif(left === '(' && right === ')') return true
}export function matchbracket(str: string): boolean {const length = str.lengthif (length === 0) return trueconst stack = []// includes 固定的长度和数据量无关const leftSymbols = '{[('const rightSymbols = '}])'for (let i = 0; i < length; i++) {const s = str[i]if(leftSymbols.includes(s)) {// 左括号,压栈stack.push(s)} else if (rightSymbols.includes(s)) {const top = stack.[stack.length - 1]if(isMatch(top, s)) {stack.pop()} else {return false}}}return stack.length === 0
}

match-bracket.test.ts

import { matchBracket } from './match-bracket'describe('括号匹配', () => {it('正常情况', () => {const str = '{a(b[c]d)e}f'const res = matchBracket(str)expect(res).toBe(true)})it('不匹配', () => {const str = '{a(b[(c]d)e}f'const res = matchBracket(str)expect(res).toBe(true)})it('顺序不一致', () => {const str = '{a(b[(c]d}e)f'const res = matchBracket(str)expect(res).toBe(true)})it('空字符串', () => {const str = ''const res = matchBracket(str)expect(res).toBe(true)})
})

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/289556.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

c语言编译和链接

一个.c源文件是如何经过处理变成可执行的.exe文件&#xff1f; 这其中经过了编译和链接两个大过程。总的来讲&#xff0c;就是每个源文件经过编译后生成对应地目标文件&#xff0c;然后所有的目标文件和所引用的标准库链接&#xff0c;形成了.exe文件。具体是怎样&#xff0c;…

TTS 文本转语音模型综合简述

本文参考文献&#xff1a; [1] Kaur N, Singh P. Conventional and contemporary approaches used in text ot speech synthesis: A review[J]. Artificial Intelligence Review, 2023, 56(7): 5837-5880. [2] TTS | 一文了解语音合成经典论文/最新语音合成论文篇【20240111更新…

代码随想录算法训练营第二十二天|235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

代码随想录算法训练营第二十二天|235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点 35.二叉搜索树的最近公共祖先 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有…

2024 ccfcsp认证打卡 2023 03 01 田地丈量

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt(); // 输入 n&#xff0c;表示矩形的数量int a in.nextInt(); // 输入 a&#xff0c;表示整个区域的长度int b in.nextInt()…

Git 常用命令速查

Git 是一个分布式版本控制系统&#xff0c;用于管理代码和其他文件。它允许您跟踪代码的更改&#xff0c;并在必要时回滚到以前的版本。 本文将介绍一些 Git 常用命令&#xff0c;帮助您快速上手 Git。 初始化 Git 仓库 git init添加文件到暂存区 git add <file_name>…

superset 二开增加 flink 数据源连接通过flink sql 查询数据

前言 superset 目前还不支持 flink 的数据源连接&#xff0c;目前我们公司在探索使用数据湖那一套东西&#xff1a; 使用 flink 作为计算引擎使用 paimon oss对象存储对接 flink 作为底层存储使用 superset 通过 flink gateway 查询 paimon 数据形成报表 增加flink数据源 …

C++零基础入门学习视频课程

教程介绍 本专题主要讲解C基础入门学习&#xff0c;所以不会涉及很深入的语法和机制。但会让你整体多面的了解和学习C的核心内容&#xff0c;快速学习使用C&#xff0c;我们的目标是先宏观整体把握&#xff0c;在深入各个击破&#xff01; 学习地址 链接&#xff1a;https:/…

简单谈谈什么是块存储?

块存储是最简单的数据存储形式&#xff0c;通常用于存储区域网络(SAN) 或 云存储 设置。文件存储在固定大小的块中&#xff0c;可以更轻松地访问文件以进行快速或频繁的编辑。虽然更复杂且成本更高&#xff0c;但存储在此类系统中的数据可以轻松访问&#xff0c;而不会影响操作…

如何在Win10使用IIS服务搭建WebDAV网站并实现无公网IP访问内网文件内容

文章目录 前言1. 安装IIS必要WebDav组件2. 客户端测试3. 使用cpolar内网穿透&#xff0c;将WebDav服务暴露在公网3.1 安装cpolar内网穿透3.2 配置WebDav公网访问地址 4. 映射本地盘符访问 前言 在Windows上如何搭建WebDav&#xff0c;并且结合cpolar的内网穿透工具实现在公网访…

docker 的八大技术架构(图解)

docker 的八大技术架构 单机架构 概念&#xff1a; 应用服务和数据库服务公用一台服务器 出现背景&#xff1a; 出现在互联网早期&#xff0c;访问量比较小&#xff0c;单机足以满足需求 架构优缺点&#xff1a; 优点&#xff1a;部署简单&#xff0c;成本低 缺点&#xff1…

80个Python数据分析必备实战案例.pdf(附代码),完全开放下载

大家好&#xff0c;我是彭涛。 随着数据时代的来临&#xff0c;Python数据分析技能现在愈加重要&#xff0c;无论是从事数据科学、商业分析还是决策支持&#xff0c;掌握 Python 数据分析的技能都将成为你事半功倍的利器。 之前为大家陆续梳理了基础资料&#xff0c;爬虫资料…

C# WPF编程-事件

C# WPF编程-路由事件 路由事件概要路由事件的三种方式 WPF事件WPF最重要的5类事件&#xff1a;生命周期事件 鼠标事件键盘事件多点触控输入原始触控 路由事件概要 路由事件是具有更强传播能力的事件&#xff0c;它们可在元素树中向上冒泡和向下隧道传播&#xff0c;并沿着传播…

网易web安全工程师进阶版课程

课程介绍 《Web安全工程师&#xff08;进阶&#xff09;》是由“ i春秋学院联合网易安全部”出品&#xff0c;资深讲师团队通过精炼的教学内容、丰富的实际场景及综合项目实战&#xff0c;帮助学员纵向提升技能&#xff0c;横向拓宽视野&#xff0c;牢靠掌握Web安全工程师核心…

【任职资格】某大型制造型企业任职资格体系项目纪实

该企业以业绩、责任、能力为导向&#xff0c;确定了分层分类的整体薪酬模式&#xff0c;但是每一名员工到底应该拿多少工资&#xff0c;同一个岗位的人员是否应该拿同样的工资是管理人员比较头疼的事情。华恒智信顾问认为&#xff0c;通过任职资格评价能实现真正的人岗匹配&…

DVB-S系统仿真学习

DVB-S系统用于卫星电视信号传输&#xff0c;发送端框图如下所示 扰码 实际数字通信中&#xff0c;载荷数据的码元会出现长连0或长连1的情况&#xff0c;不利于接收端提取时钟信号&#xff0c;同时会使得数据流中含有大量的低频分量&#xff0c;使得QPSK调制器的相位长时间不变…

中国国际通信大会2024|中国通信展览会|通信展览会

中国国际通信大会2024|中国通信展览会|通信展览会 中国国际信息通信展览会&#xff08;ICT展&#xff09;是亚太地区最具影响力的信息通信技术盛会之一。每年一度的ICT展汇聚了来自全球各行各业的专业人士&#xff0c;为各领域的科技公司、创新企业以及技术爱好者们提供一个难得…

数据结构学习——无头+单向+非循环链表增删查改实现

链表的概念及结构 概念&#xff1a;链表是一种物理存储结构上非连续、非顺序的存储结构&#xff0c;数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 注意&#xff1a; 链式结构在逻辑上是连续的&#xff0c;但是在物理上不一定连续在链表实现过程中&#xff0c;结点一…

轻松赚钱,精彩生活:上班族副业赚钱新攻略大揭秘!

薪水总是捉襟见肘&#xff0c;每月账单总让人倍感压力。你是否曾在静谧的夜晚&#xff0c;躺在床上&#xff0c;思索如何为家庭多赚一分钱&#xff1f;其实&#xff0c;你并不孤单。在这个充满机遇与挑战的时代&#xff0c;越来越多的人开始寻找副业&#xff0c;以期望让生活更…

使用easyYapi生成文档

easyYapi生成文档 背景1.安装配置1.1 介绍1.2 安装1.3 配置1.3.1 Export Postman1.3.2 Export Yapi1.3.3 Export Markdown1.3.4 Export Api1.3.6 常见问题补充 2. java注释规范2.1 接口注释规范2.2 出入参注释规范 3. 特定化支持3.1 必填校验3.2 忽略导出3.3 返回不一致3.4 设置…

PL/SQL的词法单元

目录 字符集 标识符 分隔符 注释 oracle从入门到总裁:​​​​​​https://blog.csdn.net/weixin_67859959/article/details/135209645 PL/SQL块中的每一条语句都必须以分号结束。 一个SQL语句可以跨多行&#xff0c;但分号表示该语句的结束:一行中也可以有多条 SQL语句&…