[Go 算法]20:有效括号（栈）

本月决定学习一下基础的数据结构，结合 Go 刷刷算法题目，提升算法水平的同时复习一下 Go 基础。

题外话：最近大厂裁员的消息很多，整个行情非常的低迷，我们要从现在开始准备起来！GO

放低心态、认真学习，机会总是留给不断努力的自己

题目描述

20.有效的括号

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

有效字符串需满足：

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

样例1

输入： s = “()”
输出： true

样例2

输入：s = “()[]{}”

输出：true

样例3

输入： s = “(]”
输出： false

样例4

输入：s = “([)]”
输出：false

样例5

输入：s = “{[]}”
输出：true

提示

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

解题思路分析

为什么要选择 栈 这个数据结构，我们文末给出。首先先审题一下，这里有三种不匹配的情况：

第一种情况，字符串遍历过程中，若栈内没有要匹配的字符，返回 false；

第二种情况，字符串遍历过程中，若栈内已经为空，返回 false；

第三种情况，字符串遍历完成后，但是栈不为空，说明还有未匹配的右括号，返回 false。

字符串遍历完成后，栈内空了，则说明所有的括号全部匹配成功。

分析完之后，代码其实就比较好写了，

AC 提交

其中：

• 时间复杂度：O(N)，N 是字符串 s 的长度。
• 空间复杂度：O(N)，N 是 stack & symbol 占用的空间。

结果

总结

1、之所以选择栈，是因为栈结构的特殊性，当某个数据集合只涉及在某端插入和删除数据，且满足后进者先出，先进者后出的操作特性时（LIFO），我们应该首选栈这种数据结构，非常合适做对称匹配类。

// push
stack = append(stack, s)
// pop
stack = stack[:len(stack)-1]

2、写代码之前应该先分析不匹配题目的异常情况，切记直接撸代码实现。分析题目在算法题解答中非常重要！

最后

感谢阅读，欢迎关注，后面会持续更新的。

本作品采用《CC 协议》，转载必须注明作者和本文链接