# Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
# determine if the input string is valid.
#
# The brackets must close in the correct order,
# "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
Stack:
class Solution():
def isValid(self, x):
d, stack = {"(":")", "[":"]", "{":"}"}, []
for ele in x:
if ele in d.keys(): # prefix: push
stack.append(ele)
elif not (stack and d[stack.pop()] == ele): # suffix: pop, then if cannot match, return False
return False
return len(stack) == 0
if __name__ == "__main__":
assert Solution().isValid("()[]{}") == True
assert Solution().isValid("()[{]}") == False
assert Solution().isValid("[") == False
assert Solution().isValid("]") == False