【剑指算法NO.03】20.有效的括号

题目

20.有效的括号^[1]  题目可点击「阅读原文」

记录下自己思考并最终解决这个问题的思路历程。

⚠️，前两个思路都失败了，均是不符合条件的第 2 条：左括号必须以正确的顺序闭合

【失败】思路 1：哈希表

提前准备一个 map，格式如：

一次循环字符串， 遇到开始符号“({]”时记录频率 遇到闭合符号“)}]”时减少一个 map 中开始符号对应值的数量，直到找不到开始符号就返回 false

方案通不过的原因

这个题如果像 383 赎金信一样，只求开闭符号数量一致的话，使用这个方法就好办了。可是这个题要满足两个条件：1、左括号必须用相同类型的右括号闭合。2、左括号必须以正确的顺序闭合。

第一条使用 map 这个方法是可以的。第二条，左右顺序不一致的话也可能通过（比如前期好几个不同的开始符号预录入到 map 后，后边再是乱序的闭合符号，依旧是能通过 for 循环中的判断的。

我们提到一个词“乱序”，这就是这个解法的漏洞：哈希字典表是无序的。所以从方案本身就不满足条件。

【失败】思路 2：队列

于是，有了我们的第二个解法，使用有序的数组。

循环字符串，利用两个队列，分别存放单个字符的左括号和右括号，按照顺序推进去。理想的数据如下：

循环完毕，比较两个队列 l、r，如果长度都不相等直接 false

长度相等就一一对比两个数组的对应下标成员，匹配当前位的括号是否配对、闭合。

遗憾的是：看上去思路没问题，但是提交还是发现了这个方案还是有漏洞：如：执行isValid('([)]') 当交叉符号进入队列的顺序一致、但是闭合顺序不正确时，我们的程序还是判断不出来。哭唧唧～

思路 3：使用栈的思想，后入的能闭合、就先出。

继续观察用例发现这样的规律：我们还是要按顺序遍历字符、创建一个栈空间。当我们遍历时遇到一个闭合符号时，那此时栈中最后一个字符，必须是能够匹配的“开始符号”。如用例：“[()]”当遇到“)”时，前一个一定得是“(”，否则就是整个字符串不符合条件了。

最后，当一对儿括号匹配成功、终成眷侣时，他们就该退出这个栈了 这就好比连连看，连成一对儿就要同时在地图上消失了；又像相亲节目非诚勿扰，配对儿成功的嘉宾不应该再在节目中吸引眼球了！资源，留给有需要的后来人～

最终，测试完毕，成功！

参考资料

Hi，读到这里的你～
我们有一群人（十来个吧）正在组队用JS刷 LeetCode 算法题，小队内有明确的打卡规则与惩罚制度，队员们也都每天积极的刷题打卡。如果你也想加入的话请与我联系，欢迎进来和我们一起成长。
刷题排行榜：http://123.56.222.177/
算法打卡地址：https://gitee.com/xingorg1/algorithmic-clock-out/issues