刷无止境 20 ～ 有效的括号

基本信息

• 题号：20
• 题厂：脸书
• 难度系数：低

给出一组只包含大，中，小括号的字符串，如果括号们能配对就返回 true，否则返回 false

解题思路

• 配对题，常见引用 stack 先进后出原理查询
• 本题为了书写方便，再引入 hashmap 方便查询

class Solution:
    def isValid(self, s: str) -> bool:
        # 如果要查询的字符串长度为奇数，则根本不可能配对，提前返回 false
        if len(s) % 2 == 1: return False
        
        # 初始化 stack 和 hashmap
        stack = []
        pairs = {
            "(": ")",
            "{": "}",
            "[": "]"
        }
        
        # 做 for 循环的时候，
        # 如果遇上前括号，就把对应的后括号放进 stack
        # 如果遇上后括号，将 stack 最后一个元素取出；如果能配对则 for 循环继续，如果不能配对，提前返回 false ～game over
        for i in s:
            if i in pairs:
                stack.append(pairs[i])
            elif not stack:
                return False
            else:
                pop = stack.pop()
                if pop != i:
                    return False
        
        # 做完整个 for 循环都没有返回，如果 stack 为空就返回 true，说明括号们全部配对成功……        
        return True if not stack else False

Constraints

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

解题前，可以向考官确认除了括号，还会不会有其他符号……

Big O

• Time：O（n）
• Space：引入 stack，故 O（n）

测试

• 配对括号组：‘（）’，‘（（））’
• 不配对括号组……

总结

一道比较正常的简单题，考察对 stack 的认知水平。引用 stack 后解题方案有好些，但都是大同小异的原理……

stack 常常作为解题关键出现在中难档题里，所以本题需要时常复习，深度理解如何使用 stack 解决问题……