Problem

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

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

1
2
3
Input: s = "()"
Output: true

Example 2:

1
2
3
Input: s = "()[]{}"
Output: true

Example 3:

1
2
3
Input: s = "(]"
Output: false

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

Solve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def isValid(self, s: str) -> bool:
        brackets = []

        def check(brackets):

            while len(brackets) >= 2 and is_valid( brackets[-2] , brackets[-1]  ):
                brackets.pop()
                brackets.pop()

        def is_valid(s1,s2):
            if s1 == '(' and s2 == ')':
                return True
            elif s1 == '{' and s2 == '}':
                return True
            elif s1 == '[' and s2 == ']':
                return True
            else:
                return False

        for i in range(len(s)):
            brackets.append(s[i])
            check(brackets)
        
        # 空的返回 true
        # print(brackets)
        return not brackets