20. 有效的括号

Difficulty
easy
Tags
栈
URL
https://leetcode.cn/problems/valid-parentheses/
Star
 
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
  1. 左括号必须用相同类型的右括号闭合。
  1. 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成
通过次数1,155,995提交次数2,590,494

法1 栈模拟

思路
用栈来模拟，遇到左括号直接入栈，遇到右括号，则和当前栈顶的匹配，如果不能匹配，直接返回False.
题解
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False 
            
        stack = []

        hash_map = {"(":-1, ")":1, "[":-2, "]":2, "{":-3, "}":3}

        for char in s:
            if hash_map[char] < 0:
                stack.append(char)
            else:
                if len(stack) == 0 or  hash_map[stack.pop()] + hash_map[char] != 0:
                    return False

        return True if len(stack) == 0 else False