题目描述
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
3、每个右括号都有一个对应的相同类型的左括号。
示例
示例 1:
输入:s = "()"
输出:true
示例 2:输入:s = "()[]{}"
输出:true
示例 3:输入:s = "(]"
输出:false
解题
解法一: 栈辅助法
思路
利用栈数据结构的特点(后进先出,LIFO)来模拟括号的匹配过程,确保遇到的每一个右括号都能找到对应的左括号。
- 遍历字符串:从左到右逐个遍历字符串中的每一个字符。
- 使用栈存储左括号:每当遇到一个左括号(如 '(', '[', or `'{``)时,将其压入栈中。栈用于暂存未匹配的左括号。
- 检查右括号与栈顶左括号的匹配性:当遇到一个右括号(如 ')', ']', or '}')时,检查栈是否为空以及栈顶元素是否与当前右括号匹配。若栈非空且栈顶元素与当前右括号匹配,则弹出栈顶元素;否则,字符串无效,返回 False。
- 遍历结束后的判断:遍历完整个字符串后,若栈为空,说明所有左括号都已经找到对应的右括号,字符串有效,返回 True;否则,栈中仍有未匹配的左括号,字符串无效,返回 False。
算法复杂度
时间复杂度:O(n),其中 n 为字符串 s 的长度。
由于函数对字符串 s 中的每个字符均进行一次操作,因此,该函数的时间复杂度为 O(n),其中 n 为字符串 s 的长度。
空间复杂度:O(n),其中 n 为字符串 s 的长度。
函数使用了一个栈 stack 存储遍历过程中遇到的左括号。在最坏情况下,即字符串 s 中的所有括号都是有效配对的,栈中最多存储与字符串长度相等的左括号。
代码
class Solution:def isValid(self, s: str) -> bool:# 定义一个字典,用于映射左括号到对应的右括号opening_brackets = {'(': ')', '[': ']', '{': '}'}# 初始化一个空栈,用于存储遇到的左括号stack = []# 遍历输入字符串中的每一个字符for char in s:# 当前字符为左括号时,将其压入栈中if char in opening_brackets:stack.append(char)# 当前字符为右括号,且栈非空且栈顶元素与当前右括号匹配时,# 弹出栈顶元素(表示找到了一个有效的括号对)elif stack and char == opening_brackets[stack[-1]]:stack.pop()# 当前字符为右括号,但与栈顶左括号不匹配时,字符串无效,提前返回 Falseelse:return False# 遍历完整个字符串后,若栈为空,说明所有左括号都已经找到对应的右括号,字符串有效,返回 True# 若栈不为空,说明还有未匹配的左括号,字符串无效,返回 Falsereturn not stack