Leetcode题解 - 20. 有效的括号

🔗题目描述

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

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

🔗示例

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

🔗解题思路

典型的栈应用场景，创建栈，遍历字符串，如果是左括号直接入栈，如果是右括号则判断栈顶元素是否为相同类型的左括号，如果是则执行pop操作，否则此表达式无效。

如果遍历完字符串之后栈不为空，表达式依然无效。

创建栈：

class StackNode:
    def __init__(self, value, top):
        self.value = value
        self.next = top


class Stack:
    def __init__(self):
        self.count = 0
        self.top: StackNode = None

    def push(self, node: StackNode):
        node.next = self.top
        self.count = self.count + 1
        self.top = node

    def pop(self):
        tmp: StackNode = self.top
        self.top = tmp.next
        self.count = self.count - 1
        del tmp

代码：

def isValid(self, s: str) -> bool:
    # 边界检测，空直接返回True
    if s == "":
        return True
    # 创建栈
    stack = Stack()
    # 括号匹配
    m = {
        ")": "(",
        "}": "{",
        "]": "[",
    }
    # 遍历字符串
    for c in s:
        if c == " ":
            continue
        # 如果栈空或者是左括号，则入栈
        elif stack.top is None or c in "({[":
            node = StackNode(c, stack.top)
            stack.push(node)
        else:
            # 如果括号的对应括号等于栈顶元素，则pop，否则无效
            if m[c] == stack.top.value:
                stack.pop()
            else:
                return False
    if stack.count is 0:
        return True
    else:
        return False