可视化图解算法48：有效括号序列

牛客网 面试笔试 TOP101      |       LeetCode 20. 有效的括号

1. 题目

描述

给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

数据范围：字符串长度 0≤n≤10000

要求：空间复杂度 O(n)，时间复杂度 O(n)

示例1

输入：

"()[]{}"

返回值：

true

示例2

输入：

"[]"

返回值：

true

示例3

输入：

"([)]"

返回值：

false

2. 解题思路

题目要求，字符串：仅包含：'(',')','{','}','['和']'。因此可以通过栈完成括号的匹配。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

• Python版本：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372594

• Java版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367850

• Golang版本：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1364848

3. 编码实现

核心代码如下：

var stack []uint8// 栈相关操作:
func push(v uint8) {stack = append([]uint8{v}, stack...)
}
func pop() {stack = stack[1:]
}
func top() uint8 {return stack[0]
}
func isEmpty() bool {if len(stack) <= 0 {return true}return false
}/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @return bool布尔型*/
func isValid(s string) bool {// write code here//1. 定义一个栈stack = make([]uint8, 0)for i := 0; i < len(s); i++ {//2. 如果是( [ {  ，则将对应的  )  ]  }  入栈if s[i] == '(' {push(')')} else if s[i] == '[' {push(']')} else if s[i] == '{' {push('}')} else {//3. 字符为右括号，则进行匹配检查//3.1 栈为空且字符串没有遍历完，如：))if isEmpty() {return false}//3.2 字符串内容与栈顶元素不一致，则不匹配，如：(]if s[i] != top() {return false}//3.3 每正确匹配一个，出栈一个元素，进行一下对括号的匹配pop()}}if isEmpty() {// 4. 所有字符串匹配完，且栈中没有元素，则说明括号匹配return true}//5. 所有字符串匹配完，栈中还有元素，则证明不匹配。如：()[return false}

具体完整代码你可以参考下面视频的详细讲解。

• Python版本：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372594

• Java版本：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367850

• Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364848

4.小结

括号序列的判断方法为：遍历字符串中的括号字符，如果是左括号则将对应的右括号入栈；如果是右括号则弹出栈顶的元素与字符串内容进行匹配。完全匹配的条件是：字符串中的内容取完且栈中没有元素。

《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：

  ✅   链表

  ✅   二叉树

  ✅   二分查找、排序

  ✅   堆、栈、队列

  ✅   回溯算法

  ✅   哈希算法

  ✅   动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss897667807

• Java编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss161443488

• Golang编码实现：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss63997

对于数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：人面不知何处去，桃花依旧笑春风。