【LeetCode09】有效的括号

今日挑战

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

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"输出: true

示例 2:

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

示例 3:

输入: "(]"输出: false

示例 4:

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

示例 5:

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

这道题很有意思，其实它和我们的日常写sql很有联系，就是当我们写漏或者写多括号的时候，编辑器会提示我们错误，而我们这道题，就是实现这个功能。

先思考一下，后面我会给出一个解题思路～?

图来自网络

这道题目，我们会用到栈的知识点，在使用栈之前，我们先说明一下一些名词。

• 左括号：指的是区间左边的括号，比如 { [ ( 之类的；
• 右括号：指的是区间右边的括号，比如 } ] ) 之类的；
• 栈：又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

我们大致通过下面的步骤来实现：

1 ）初始化栈 S；

2 ）依次遍历所有的括号，如果遇到左括号，我们只需将其推到栈上即可；

3 ）如果我们遇到一个右括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效；

4 ）如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。

大家可以看下我画的示意图：

Python实现：

def isValid(s):

    # 初始化一个栈
    stack = []

    # 设置左右括号的对应关系
    mapping = {")": "(", "}": "{", "]": "["}

    # 遍历所有的元素（即括号）
    for char in s:

        # 当前元素为右括号
        if char in mapping:

            # 抽取当前栈的栈顶元素，如果为空，则赋值为 #
            top_element = stack.pop() if stack else '#'

            # 如果栈顶元素不等于当前的右括号对应的左括号，则直接返回 False
            if mapping[char] != top_element:
                return False

        # 当前元素为左括号
        else:
            # 直接放入栈顶
            stack.append(char)

    # 最后如果栈为空，代表表达式有效
    return not stack

? 配图角色背景介绍

冬日战士（Winter Soldier）是美国漫威漫画旗下超级英雄，初次登场于《美国队长》（Captain America）第1期（1941年3月），作为冬日战士首次出现于《美国队长》第5卷第1期（2005年1月），由乔·西蒙以及杰克·科比联合创造。本名詹姆斯·布坎南·巴恩斯 / 巴基·巴恩斯（James Buchan Barnes / Bucky Barnes），是美国队长在二战中最亲密的战友和最坚实的后盾，后来在二战尾声的一次行动中，与队长一同掉入大海之中被冰封。但是不同的是，九头蛇的人发现并解冻了他，还在他的断臂处安装上了机械手臂，并将其洗脑训练成了只效忠九头蛇的特工“冬日战士”（Winter Soldier）。此后巴基以冬日战士的身份为邪恶组织九头蛇在世界各地完成各种刺杀任务，后在与复仇者成员多次较量中恢复记忆，背叛了九头蛇，并被好友美国队长邀请加入复仇者联盟。