当前位置：首页 > article >正文

【代码随想录】刷题记录(31)-有效的括号

article 2024/11/17 21:30:07

题目描述：

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

有效字符串需满足：

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

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

提示：

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

我的作答：

呃呃呃简单题我也写了一个小时，跳楼了。。。。。

class Solution(object):
    def __init__(self):
        self.st = []

    def push(self,x):
        self.st.append(x)

    def pop(self):
        if self.empty():
            return None
        else:
            return self.st.pop()

    def top(self):
        if self.empty():
            return None
        else:
            return self.st[-1]

    def empty(self):
        return not self.st

    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s)%2!=0: #剪枝操作，如果是奇数绝对括号不匹配，但是如果是偶数也不一定匹配：{{
            return False
        for i in range(len(s)):
            if s[i]=='(': #如果是左括号，就给栈推入对应的右括号，便于后面查看是否对应
                self.push(')')
            elif s[i]=='[':
                self.push(']')
            elif s[i]=='{':
                self.push('}')
            elif self.empty() or s[i]!=self.top(): #如果遍历还没结束栈就空了说明左括号多了
                return False                       #如果访问的右括号和栈里的不一样直接返回f
            else:
                self.pop() #表示访问的是s里面的右括号且无异常发生
        return self.empty() #如果栈刚好空了，说明一一对应消去了

只存在三种不匹配的情况：

（1）左括号多了；

（2）左右括号数量相等，但是对应位置存在不匹配的括号；

（3）右括号多了；

由于左右括号在对应的位置必须要对应，根据这个逻辑，当访问一个左括号的时候，储存对应的右括号在栈里，就相当于又储存了括号类型又储存了括号位置，因而当访问s里对应右括号的位置时，此时栈弹出的就是理论上左括号对应的正确右括号类型！

参考代码：（啊啊啊啊好简洁）

# 方法一，仅使用栈，更省空间
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item:
                return False
            else:
                stack.pop()
        
        return True if not stack else False

# 方法二，使用字典
class Solution:
    def isValid(self, s) :
        stack = []
        mapping = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        for item in s:
            if item in mapping.keys():
                stack.append(mapping[item])
            elif not stack or stack[-1] != item: 
                return False
            else: 
                stack.pop()
        return True if not stack else False