有效的括号

这个题解使用了栈的数据结构来判断括号的有效性。具体思路如下： 1. 首先判断字符串长度是否为奇数，如果是奇数则一定不是有效的括号，直接返回 false。 2. 计算字符串长度的一半 half，作为左括号数量的上限。 3. 遍历字符串中的每个字符： - 如果当前字符是左括号，则将其压入栈中，并检查栈的大小是否超过 half，如果超过则说明左括号数量过多，直接返回 false。 - 如果当前字符是右括号，则检查栈是否为空，如果为空则说明没有与之匹配的左括号，直接返回 false。然后检查栈顶元素是否与当前右括号匹配，如果不匹配则直接返回 false，否则将栈顶元素弹出。 4. 遍历完成后，检查栈是否为空，如果为空则说明所有括号都正确匹配，返回 true，否则返回 false。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def isValid(self, s: str) -> bool:
        # 如果字符串长度为奇数，一定不是有效的括号
        if len(s) % 2 == 1:
            return False
        
        # 计算字符串长度的一半，作为左括号数量的上限
        half = len(s) // 2
        
        stack = []
        left = set('([{')  # 用集合存储左括号，便于判断
        for char in s:
            if char in left:
                stack.append(char)  # 如果是左括号，压入栈中
                # 如果栈的大小超过一半，说明左括号数量过多
                if len(stack) > half:
                    return False
            else:
                # 如果栈为空，说明没有与之匹配的左括号
                if len(stack) == 0:
                    return False
                # 检查栈顶元素是否与当前右括号匹配
                if char == ')' and stack[-1] != '(':
                    return False
                if char == ']' and stack[-1] != '[':
                    return False
                if char == '}' and stack[-1] != '{':
                    return False
                stack.pop()  # 如果匹配，弹出栈顶元素
        
        # 如果栈为空，说明所有括号都正确匹配
        return len(stack) == 0