leetcode-solution/Python/0020-valid-parentheses.py at main · hogan-tech/leetcode-solution · GitHub

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
30
31
32
33
34
35
36
37
38
39
40
41
42
# time complexity: O(n)
# space complexity: O(n)
class Solution:
    def isValid(self, s: str) -> bool:
        bracketMap = {"(": ")", "[": "]", "{": "}"}
        openSet = set(["(", "[", "{"])
        stack = []
        for char in s:
            if char in openSet:
                stack.append(char)
            elif stack and char == bracketMap[stack[-1]]:
                stack.pop()
            else:
                return False
        return stack == []

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c in '{[(':
                stack.append(c)
            elif c == ')' and stack and stack[-1] == '(':
                stack.pop()
            elif c == ']' and stack and stack[-1] == '[':
                stack.pop()
            elif c == '}' and stack and stack[-1] == '{':
                stack.pop()
            else:
                return False
        return len(stack) == 0

s = "()"
print(Solution().isValid(s))
s = "()[]{}"
print(Solution().isValid(s))
s = "(]"
print(Solution().isValid(s))
s = "([])"
print(Solution().isValid(s))
s = "([)]"
print(Solution().isValid(s))