有效括号序列

有效括号序列_牛客题霸_牛客网

问题简述

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

思路：栈

• 遇到左括号入栈，否则出栈；

  • 出栈时，看括号是否匹配；

• 无效条件，中途遇到了不匹配的括号；最后栈不为空；

• 小技巧：

  • 遇到左括号，可以压栈对应的右括号，这样出栈匹配时做等值比较就可以了；

  • 奇数串直接返回 False；

Python

class Solution:
    def isValid(self, s: str) -> bool:
        
        if len(s) & 1: return False
        
        stk = []
        book = {'(': ')', '[': ']', '{': '}'}
        
        for c in s:
            if c in book:
                stk.append(book[c])
            else:
                if not stk or stk[-1] != c:
                    return False
                stk.pop()
        
        return False if stk else True