1
class MinStack:
2

3
    def __init__(self):
4
        self.stack = [(0, float("inf"))]
5

6
    def push(self, value: int) -> None:
7
        self.stack.append((value, min(self.stack[-1][1], value)))
8

9
    def pop(self) -> None:
10
        self.stack.pop()
11

12
    def top(self) -> int:
13
        return self.stack[-1][0]
14

15
    def getMin(self) -> int:
16
        return self.stack[-1][1]

1
class Solution:
2
    def isValid(self, s: str) -> bool:
3
        stack = []
4
        need = {
5
            "}" : "{",
6
            "]" : "[",
7
            ")" : "("
8
        }
9
        for c in s:
10
            if c == '(' or c == '[' or c == '{':
11
                stack.append(c)
12
            else:
13
                if not stack:
14
                    return False
15
                if stack[-1] != need[c]:
16
                    return False
17
                stack.pop()
18
        return not stack