20.有效的括号

题目链接

https://leetcode.cn/problems/valid-parentheses

解题思路

使用栈

• 若仍有字符
  • 碰到左括号, 入栈
  • 碰到右括号, 弹出栈顶元素
    • 如果栈为空, 返回False <-- 对应右括号多余
    • 如果栈非空
      • 如果右括号不匹配, 返回False <-- 对应左右括号不匹配
• 若没有字符
  • 栈非空, 返回False <-- 对应左括号多余
  • 栈为空: 返回True

py1

# ⌚ 65ms 📀 16.3MB
class Solution:
    def isValid(self, s: str) -> bool:
        stacks = []
        dict = {"(": ")", "[": "]", "{": "}"}
        for i in range(len(s)):
            if s[i] in ["(", "[", "{"]:
                stacks.append(s[i])
            else:
                try:
                    top = stacks.pop()
                except IndexError:
                    return False # 右括号多余
                else:
                    if s[i] != dict[top]:
                        return False # 左右括号不匹配
        if len(stacks) != 0:
            return False # 左括号多余
        return True

py2

# ⌚ 42ms 📀 16.45MB
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        pairs = {
            ")": "(",
            "]": "[",
            "}": "{"
        }
        stack = list()
        for ch in s:
            if ch in pairs:
                if not stack or stack[-1] != pairs[ch]: # 右括号多余 | 左右括号不匹配
                    return False
                stack.pop()
            else:
                stack.append(ch)
        return not stack # 左括号多余

使用replace函数

由于题目中指明了括号是无法嵌套的, 所以还可以使用replace函数将括号替换为空字符, 检查最后的字符串是否为空, 若为空, 则返回True, 若非空, 返回False.

# ⌚ 60ms 📀 16.39MB
class Solution:
    def isValid(self, s: str) -> bool:
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''

这种方法无法适用于嵌套的情况, 故不推荐.