leetcode20 Valid Parentheses

原题链接 https://leetcode.com/problems/valid-parentheses/

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true
Example 2:

Input: "()[]{}"
Output: true
Example 3:

Input: "(]"
Output: false

括号匹配有先进后出的特征，这里用栈对其进行匹配确认。字符可能属于括号，也可能不属于，各种情况都要考虑到。

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) & 1 == 1:
            return False
        dicts = {"(":")", "{":"}", "[":"]"}
        stack = []
        
        for i in range(len(s)):
            if s[i] in "([{":
                stack.append(s[i])
            elif s[i] in "}])":
                if stack and dicts[stack[-1]] == s[i]:
                    stack.pop()
                else:
                    return False
            else:
                return False
        return not stack