前端|LeetCode20_有效的括号

2020-02-11

题目描述

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

有效字符串需满足:

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

注意空字符串可被认为是有效字符串。

解题思路

拿到题目,第一件事情,就是先把问题分解,从题目描述中可以看出要对三种类型的组合括号进行判断,那我们就先考虑一种括号的情况。题目中提到的注意空字符,也可以先不考虑。

分解后的题目描述

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

有效字符串需满足:

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

思路

现在题目就变得更加简单了,因为只有这一种类型的符号,我们不用考虑括号类型是否正确。核心的问题就是如何判断括号的顺序是否正确。

那如何判断括号的顺序是否正确呢?

括号只有左括号和右括号两种,左括号在左边,右括号在右边即为正确的顺序,其他的顺序都是错误的。

使用栈后进先出的特性,先把左括号推入栈中,等到遇到右括号的时候,把左括号从栈推出,和右括号进行比较,如果两个括号匹配,那就证明这一对括号是正确的,接下来重复上述操作,直到没有右括号,退出循环。退出循环后检查栈中是否还有括号存在,如果栈为空,则证明所有括号都配对完成,反之,则证明字符串不是有效的。

解决了一个类型的括号后,遇到多个类型的括号,只要在判断括号是否匹配的时候去检测一下是否是配对括号即可。

实现

Untitled (3).jpeg

原文链接:segmentfault.com

上一篇:JavaScript优雅写法及骚操作
下一篇:用pixi.js制作拼图游戏
相关教程
关注微信

扫码加入 JavaScript 社区

相关文章

首次访问,需要验证
微信扫码,关注即可
(仅需验证一次)

欢迎加入 JavaScript 社区

号内回复关键字:

回到顶部