Python面试宝典第6题:有效的括号

题目

        给定一个只包括 '('、')'、'{'、'}'、'['、']' 这些字符的字符串,判断该字符串是否有效。有效字符串需要满足以下的条件。

        1、左括号必须用相同类型的右括号闭合。

        2、左括号必须以正确的顺序闭合。

        3、每个右括号都有一个对应的相同类型的左括号。

        注意:空字符串可被认为是有效字符串。

        示例 1:

输入: "([])"
输出: true

        示例 2:

输入: "()[]{}"
输出: true

        示例 3:

输入: "(]"
输出: false

        示例 4:

输入: "([)]"
输出: false

递归法

        本题可以采用递归的方式来解决,递归的基本思想是不断地将问题分解为更小的子问题。对于当前的字符串,如果它是有效括号字符串,那么它要么为空,要么可以分为两部分:第一个部分包含一个左括号、一个有效括号字符串、一个对应的右括号,第二部分包含另一个有效括号字符串(如果存在的话)。通过这种方式,我们可以递归地检查字符串的每一部分是否有效。使用递归法求解本题的主要步骤如下。

        1、如果字符串为空,直接返回true,因为空字符串视为有效。

        2、如果字符串长度为奇数,直接返回false,因为有效的括号字符串长度必须是偶数。

        3、从字符串的第一个字符开始,找到第一个闭合的括号对(即左括号和其对应的右括号)。如果找不到成对的括号,说明字符串无效,返回false。

        4、将字符串分割为两部分:中间的有效括号对、右边的子字符串(从找到的右括号之后的部分)。

        5、递归地检查子字符串是否有效,如果都有效,则整个字符串有效。否则,无效。

        注意:虽然递归法在理论上可行,但它在处理长字符串时,可能会导致调用栈溢出。递归法更多地是作为一种算法思维的展示,帮助理解问题的分解过程,故这里就不给出具体的源码实现了。

栈方法

        对于括号匹配问题,最直观的方法是使用栈数据结构来解决。首先遍历整个字符串,每次遇到左括号时,将其压入栈中。每次遇到右括号时,检查栈顶元素是否为对应的左括号。如果是,则弹出栈顶元素,继续遍历。如果不是,则直接判定该字符串无效。遍历结束后,如果栈为空,则说明所有括号都已正确匹配。使用栈方法求解本题的主要步骤如下。

        1、初始化一个空栈。

        2、遍历字符串中的每一个字符,做如下判断。

        (1)如果字符是'('、'{' 、'[',将其压入栈中。

        (2)如果字符是')'、'}' 、']',检查栈顶元素是否为其对应的左括号。如果是,弹出栈顶元素。如果不是,直接返回false。

        3、遍历完成后,检查栈是否为空。为空则返回true,表示所有括号都已正确匹配。不为空则返回false,表示存在未匹配的括号。

        根据上面的算法步骤,我们可以得出下面的示例代码。

def is_valid_brackets(s: str) -> bool:
    bracket_map = {")": "(", "}": "{", "]": "["}
    stack = []
    
    for char in s:
        if char in bracket_map:
            # 如果栈为空,或者栈顶元素不是对应的左括号,返回false
            if not stack or stack[-1] != bracket_map[char]:
                return False
            stack.pop()  # 匹配成功,弹出栈顶元素
        else:
            # 左括号直接入栈
            stack.append(char)
    
    return not stack  # 栈为空则返回true,表示所有括号都已正确匹配

# 输出:True
print(is_valid_brackets("([])"))
# 输出:True
print(is_valid_brackets("()[]{}"))
# 输出:False
print(is_valid_brackets("(]"))
# 输出:False
print(is_valid_brackets("([)]"))

总结

        使用栈结构处理括号匹配问题的时间复杂度是O(n),空间复杂度也是O(n)。在处理括号匹配这类问题时,栈结构是极其高效且直观的选择。它能够自然地处理“后进先出”的特性,完美符合括号匹配的场景。

上一篇:设置和取消Excel“打开密码”的3种方法


下一篇:OceanBase Meetup北京站|跨行业应用场景中的一体化分布式数据库:AI赋能下的探索与实践